MATH 409 Lecture 8

« previous | Thursday, September 19, 2013 | next »

Lecture Slides

New Challenges

Challenge 7

Build a sequence $\left\{x_{n}\right\}$ of real numbers such that every real number is a limit point of $\left\{x_{n}\right\}$ (a limit point f a sequence is, by definition, the limit of a convergent subsequence).

Challenge 8

Let $\left\{F_{n}\right\}$ be the sequence of Fibbonacci numbers. Prove that

$\lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}={\frac {{\sqrt {5}}+1}{2}}$

Review

• MATH 409 Lecture 7#Monotone Sequences

Examples

Theorem. If $0<a<1$, then $a^{n}\to 0$ as $n\to \infty$.

Proof. Since $a<1$ and $a>0$, it follows that $a^{n+1}<a^{n}$ and $a^{n}>0$ for all $n\in \mathbb {N}$. Hence the sequence $\left\{a^{n}\right\}$ is strictly decreasing and bounded. Therefore it converges to some $x\in \mathbb {R}$.

Since $a^{n+1}=a^{n}\,a$ for all $n$, it follows that $a^{n+1}\to x\,a$ as $n\to \infty$. However, $\left\{a^{n+1}\right\}$ is a subsequence of $\{a^{n}\}$, hence it converges to the same limit as $\left\{a^{n}\right\}$. Thus $x\,a=x$, which implies that $x=0$.

quod erat demonstrandum

Theorem. If $a>1$, then $a^{n}\to +\infty$ as $n\to \infty$.

Proof. Since $a>1$, it follows that $a^{n+1}>a^{n}>1$ for all $n\in \mathbb {N}$. Hence $\left\{a^{n}\right\}$ is strictly increasing. Then $\left\{a^{n}\right\}$ either diverges to $+\infty$ or converges to a limit $x$. In the latter case, we argue as above to obtain that $x=0$. However, this contradicts with $a^{n}>1$. Thus $\left\{a^{n}\right\}$ diverges to $+\infty$.

quod erat demonstrandum

Theorem. If $a>0$, then ${\sqrt[{n}]{a}}\to 1$ as $n\to \infty$.

Observe that by definition, ${\sqrt[{n}]{a}}$ is a unique positive number $r$ such that $r^{n}=a$.

Proof. If $a\geq 1$, then $a^{n+1}\geq a^{n}\geq 1$ for all $n\in \mathbb {N}$, which implies that ${\sqrt[{n(n+1)}]{a^{n+1}}}\geq {\sqrt[{n(n+1)}]{a^{n}}}\geq 1$. Notice that ${\sqrt[{n(n+1)}]{a^{n+1}}}={\sqrt[{n}]{a}}$ and ${\sqrt[{n(n+1)}]{a^{n}}}={\sqrt[{n+1}]{a}}$. Hence ${\sqrt[{n}]{a}}\geq {\sqrt[{n+1}]{a}}\geq 1$ for all $n$.

Similarly, in the case $0<a<1$, we obtain that ${\sqrt[{n}]{a}}<{\sqrt[{n+1}]{a}}<1$ for all $n$. In either case, the sequence $\left\{{\sqrt[{n}]{a}}\right\}$ is monotone and bounded. Therefore it converges to a limit $x$. Then the sequence $\left\{{\sqrt[{2n}]{a}}\right\}$ also converges to $x$ since it is a subsequence of $\left\{{\sqrt[{n}]{a}}\right\}$. At the same time, $\left({\sqrt[{2n}]{a}}\right)^{2}={\sqrt[{n}]{a}}$, which implies that $x^{2}=x$. Hence $x\in \{0,1\}$. However, the limit cannot be 0 since ${\sqrt[{n}]{a}}\geq \min {(a,1)}>0$ (the first element sets the lower bound of an increasing function). Thus the limit is 1.

quod erat demonstrandum

Theorem. The sequence $x_{n}=\left(1+{\frac {1}{n}}\right)^{n}$ for $n\in \mathbb {N}$ is increasing and bounded, hence it is convergent.

Note: The limit is the number $\mathrm {e} =2.71828\ldots$

Proof. First let us show that $\left\{x_{n}\right\}$ is increasing. For any $n\in \mathbb {N}$,

${\begin{aligned}x_{n}&=\left(1+{\frac {1}{n}}\right)^{n}\\&=\left({\frac {n+1}{n}}\right)^{n}\\&={\frac {(n+1)^{n}}{n^{n}}}\end{aligned}}$

If $n\geq 2$, then similarly

$x_{n-1}={\frac {n^{n-1}}{(n-1)^{n-1}}}$

Hence

${\begin{aligned}{\frac {x_{n}}{x_{n-1}}}&={\frac {(n+1)^{n}}{n^{n}}}\cdot {\frac {(n-1)^{n-1}}{n^{n-1}}}\\&=\left({\frac {(n+1)(n-1)}{n^{2}}}\right)^{n-1}\cdot {\frac {n+1}{n}}\\&=\left({\frac {n^{2}-1}{n^{2}}}\right)^{n-1}\cdot {\frac {n+1}{n}}\\&=\left(1-{\frac {1}{n^{2}}}\right)^{n-1}\,\left(1+{\frac {1}{n}}\right)\end{aligned}}$

To continue, we need the following lemma:

Lemma. If $0<x<1$, then $(1-x)^{k}\geq 1-k\,x$ for all $k\in \mathbb {N}$.

Proof by induction. Basis. For $k=1$, we have $(1-x)^{1}=1-1\cdot x$.

Induction. Assume $\left(1-x\right)^{k}\geq 1-k\,x$ for some $k\in \mathbb {N}$ and all $x\in (0,1)$. Then

${\begin{aligned}(1-x)^{k+1}&=\left(1+x\right)^{k}\,(1-x)\\&\geq (1-k\,x)\,(1-x)\\&=1-k\,x-x+k\,x^{2}>1-(k+1)\,x\end{aligned}}$

Thus the lemma holds by induction on $k$.

Remark. According to the binomial formula,

$(1-x)^{k}=1-k\,x+{\frac {k(k-1)}{2}}\,x^{2}-\ldots$

Using this lemma, we obtain that

${\begin{aligned}{\frac {x_{n}}{x_{n-1}}}&=\left(1-{\frac {1}{n^{2}}}\right)^{n-1}\,\left(1+{\frac {1}{n}}\right)\\&\geq \left(1-{\frac {n-1}{n^{2}}}\right)\,\left(1+{\frac {1}{n}}\right)\\&=1-{\frac {n-1}{n^{2}}}+{\frac {1}{n}}-{\frac {n-1}{n^{3}}}\\&=1+{\frac {1}{n^{2}}}-{\frac {n-1}{n^{3}}}\\&=1+{\frac {1}{n^{3}}}>1\end{aligned}}$

Thus the sequence $\left\{x_{n}\right\}$ is strictly increasing.

---

Now let us show that the sequence $\left\{x_{n}\right\}$ is bounded. Since $\left\{x_{n}\right\}$ is increasing, it is enough to show that it is bounded above. By the binomial formula,

${\begin{aligned}x_{n}&=\left(1+{\frac {1}{n}}\right)^{n}\\&=\sum _{k=0}^{n}{\binom {n}{k}}\,\left({\frac {1}{n}}\right)^{k}\\&=\sum _{k=0}^{n}{\frac {n!}{k!(n-k)!}}\,\left({\frac {1}{n}}\right)^{k}\\\end{aligned}}$

Observe that ${\frac {n!}{k!(n-k)!}}\,\left({\frac {1}{n}}\right)^{k}\leq 1$ for all $0\leq k\leq n$ because

${\frac {n!}{k!(n-k)!}}\,\left({\frac {1}{n}}\right)^{k}={\frac {n(n-1)\dots (n-k+1)}{n\cdot n\dots n}}$

Note there are $k$ terms in both the numerator and the denominator, and the denominator is obviously larger.

It follows that $x_{n}\leq \sum _{k=0}^{n}{\frac {1}{k!}}=1+{\frac {1}{1!}}+\dots +{\frac {1}{n!}}$

Further observe that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k! \ge 2^{k-1}} for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k \ge 0} because Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 \cdot 2 \cdot 3 \dots k \ge 2 \cdot 2 \dots 2} . There are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k-1} factors greater than 2 on the LHS, and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k-1} factors equal to 2 on the RHS.

Therefore we obtain

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} x_n &\le 1 + 1 + \frac{1}{2} + \frac{1}{2^2} + \dots + \frac{1}{2^{n-1}} \\ &= 3 - \frac{1}{2^{n-1}} \\ &\le 3 \end{align}}

So the sequence is bounded.

quod erat demonstrandum

Cauchy Sequences

A sequence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ x_n \right\}} of real numbers is called a Cauchy sequence if, for any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon > 0} , there exists Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N \in \mathbb{N}} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| x_n - x_m \right| < \epsilon} whenever Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n,m \ge N} .

Note that the definition of cauchy sequences is redundant with equivalent to the theorem regarding convergent of sequences, only cauchy sequences do not need a limit to prove they converge.

Theorem. Any convergent sequence is Cauchy.

Proof. Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ x_n \right\}} be a convergent sequence and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} be its limit. Then for any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon > 0} there exists Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N \in \mathbb{N}} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| x_n - a \right| < \frac{\epsilon}{2}} whenever Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \ge N} . Now for any natural numbers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n,m \ge N} we have

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| x_n -x_m \right| = \left| x_n - a + a - x_m \right| \le \left| x_n - a \right| + \left| x_m - a \right| < \frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon }

Thus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ x_n \right\}} is a Cauchy sequence.

quod erat demonstrandum

Theorem. Any Cauchy sequence is convergent.

Proof. (proved by Cauchy, but he called them fundamental sequences) Suppose Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ x_n \right\}} is a Cauchy sequence. First let us show that the sequence is bounded. Since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ x_n \right\}} is Cauchy, there exists Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N \in \mathbb{N}} such that $\left|x_{n}-x_{m}\right|<1$ whenever Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n,m \ge N} . In particular, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| x_n - x_N \right| < 1} for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \ge N} . Then

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |x_n| = \left| \left( x_n - x_N \right) + x_N \right| \le |x_n - x_N| + |x_N| < |x_N| + 1}

It follows that for any natural number $n$, we have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |x_n| \le M} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M = \max{(|x_1|, |x_2|, \ldots, |x_{N-1}|, |x_N|+1)}} .

Now the Bolzano-Weierstrass theorem implies that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ x_n \right\}} has a subsequence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ x_{n_k} \right\}_{k \in \mathbb{N}}} converging to some $a\in \mathbb {R}$. Given Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon > 0} , there exists Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_\epsilon \in \mathbb{N}} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| x_{n_k} - a \right| < \frac{\epsilon}{2}} for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k \ge K_\epsilon} . Also, there exists $N_{\epsilon }\in \mathbb {N}$ such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| x_n - x_m \right| < \frac{\epsilon}{2}} whenever Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n,m \ge N_\epsilon} . Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k = \max{(K_\epsilon, N_\epsilon)}} . Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k \ge K_\epsilon} and $n_{k}\geq k\geq N_{\epsilon }$. Therefore for any $n\geq N_{\epsilon }$, we obtain

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| x_n - a \right| = \left| \left( x_n - x_{n_k} \right) + \left( x_{n_k} - a \right) \right| \le \left| x_n - x_{n_k} \right| + \left| x_{n_k} - a \right| < \frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon}

Thus the entire sequence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ x_n \right\}} converges to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} .

quod erat demonstrandum

Limit Points

A limit point of a sequence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ x_n \right\}} is the limit of any convergent subsequence of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ x_n \right\}} .

• A convergent sequence has only one limit point, its limit.
• Any bounded sequence has at least one limit point (by Bolzano-Wierstrass theorem)
• If a bounded sequence is not convergent, then it has at least two limit points.
• The sequence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ \left( -1 \right)^n \right\}} has 2 limit points, namely 1 and −1
• If all elements of a sequence belong to a closed interval Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left[ a,b \right]} , then all its limits belong to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left[ a,b \right]} as well (by comparison theorem)
• The set of limit points of the sequence $\left\{\sin {n}\right\}$ is the entire interval Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left[ -1,1 \right]} (key: π is irrational)
• If a sequence diverges to infinity, then it has no limit points
• If a sequence does not diverge to infinity, then it has a bounded subsequence and hence it has a limit point.