# MATH 409 Lecture 8

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

Lecture Slides

## New Challenges

### Challenge 7

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

### Challenge 8

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

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

## Review

### Examples

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

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

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

quod erat demonstrandum

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

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

quod erat demonstrandum

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

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

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

Similarly, in the case ${\displaystyle 0, we obtain that ${\displaystyle {\sqrt[{n}]{a}}<{\sqrt[{n+1}]{a}}<1}$ for all ${\displaystyle n}$. In either case, the sequence ${\displaystyle \left\{{\sqrt[{n}]{a}}\right\}}$ is monotone and bounded. Therefore it converges to a limit ${\displaystyle x}$. Then the sequence ${\displaystyle \left\{{\sqrt[{2n}]{a}}\right\}}$ also converges to ${\displaystyle x}$ since it is a subsequence of ${\displaystyle \left\{{\sqrt[{n}]{a}}\right\}}$. At the same time, ${\displaystyle \left({\sqrt[{2n}]{a}}\right)^{2}={\sqrt[{n}]{a}}}$, which implies that ${\displaystyle x^{2}=x}$. Hence ${\displaystyle x\in \{0,1\}}$. However, the limit cannot be 0 since ${\displaystyle {\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 ${\displaystyle x_{n}=\left(1+{\frac {1}{n}}\right)^{n}}$ for ${\displaystyle n\in \mathbb {N} }$ is increasing and bounded, hence it is convergent.

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

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

{\displaystyle {\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 ${\displaystyle n\geq 2}$, then similarly

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

Hence

{\displaystyle {\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 ${\displaystyle 0, then ${\displaystyle (1-x)^{k}\geq 1-k\,x}$ for all ${\displaystyle k\in \mathbb {N} }$.

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

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

{\displaystyle {\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 ${\displaystyle k}$.

Remark. According to the binomial formula,

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

Using this lemma, we obtain that

{\displaystyle {\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 ${\displaystyle \left\{x_{n}\right\}}$ is strictly increasing.

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

{\displaystyle {\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 ${\displaystyle {\frac {n!}{k!(n-k)!}}\,\left({\frac {1}{n}}\right)^{k}\leq 1}$ for all ${\displaystyle 0\leq k\leq n}$ because

${\displaystyle {\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 ${\displaystyle k}$ terms in both the numerator and the denominator, and the denominator is obviously larger.

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

Further observe that ${\displaystyle k!\geq 2^{k-1}}$ for all ${\displaystyle k\geq 0}$ because ${\displaystyle 1\cdot 2\cdot 3\dots k\geq 2\cdot 2\dots 2}$. There are ${\displaystyle k-1}$ factors greater than 2 on the LHS, and ${\displaystyle k-1}$ factors equal to 2 on the RHS.

Therefore we obtain

{\displaystyle {\begin{aligned}x_{n}&\leq 1+1+{\frac {1}{2}}+{\frac {1}{2^{2}}}+\dots +{\frac {1}{2^{n-1}}}\\&=3-{\frac {1}{2^{n-1}}}\\&\leq 3\end{aligned}}}

So the sequence is bounded.

quod erat demonstrandum

## Cauchy Sequences

A sequence ${\displaystyle \left\{x_{n}\right\}}$ of real numbers is called a Cauchy sequence if, for any ${\displaystyle \epsilon >0}$, there exists ${\displaystyle N\in \mathbb {N} }$ such that ${\displaystyle \left|x_{n}-x_{m}\right|<\epsilon }$ whenever ${\displaystyle n,m\geq 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 ${\displaystyle \left\{x_{n}\right\}}$ be a convergent sequence and ${\displaystyle a}$ be its limit. Then for any ${\displaystyle \epsilon >0}$ there exists ${\displaystyle N\in \mathbb {N} }$ such that ${\displaystyle \left|x_{n}-a\right|<{\frac {\epsilon }{2}}}$ whenever ${\displaystyle n\geq N}$. Now for any natural numbers ${\displaystyle n,m\geq N}$ we have

${\displaystyle \left|x_{n}-x_{m}\right|=\left|x_{n}-a+a-x_{m}\right|\leq \left|x_{n}-a\right|+\left|x_{m}-a\right|<{\frac {\epsilon }{2}}+{\frac {\epsilon }{2}}=\epsilon }$

Thus ${\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 ${\displaystyle \left\{x_{n}\right\}}$ is a Cauchy sequence. First let us show that the sequence is bounded. Since ${\displaystyle \left\{x_{n}\right\}}$ is Cauchy, there exists ${\displaystyle N\in \mathbb {N} }$ such that ${\displaystyle \left|x_{n}-x_{m}\right|<1}$ whenever ${\displaystyle n,m\geq N}$. In particular, ${\displaystyle \left|x_{n}-x_{N}\right|<1}$ for all ${\displaystyle n\geq N}$. Then

${\displaystyle |x_{n}|=\left|\left(x_{n}-x_{N}\right)+x_{N}\right|\leq |x_{n}-x_{N}|+|x_{N}|<|x_{N}|+1}$

It follows that for any natural number ${\displaystyle n}$, we have ${\displaystyle |x_{n}|\leq M}$, where ${\displaystyle M=\max {(|x_{1}|,|x_{2}|,\ldots ,|x_{N-1}|,|x_{N}|+1)}}$.

Now the Bolzano-Weierstrass theorem implies that ${\displaystyle \left\{x_{n}\right\}}$ has a subsequence ${\displaystyle \left\{x_{n_{k}}\right\}_{k\in \mathbb {N} }}$ converging to some ${\displaystyle a\in \mathbb {R} }$. Given ${\displaystyle \epsilon >0}$, there exists ${\displaystyle K_{\epsilon }\in \mathbb {N} }$ such that ${\displaystyle \left|x_{n_{k}}-a\right|<{\frac {\epsilon }{2}}}$ for all ${\displaystyle k\geq K_{\epsilon }}$. Also, there exists ${\displaystyle N_{\epsilon }\in \mathbb {N} }$ such that ${\displaystyle \left|x_{n}-x_{m}\right|<{\frac {\epsilon }{2}}}$ whenever ${\displaystyle n,m\geq N_{\epsilon }}$. Let ${\displaystyle k=\max {(K_{\epsilon },N_{\epsilon })}}$. Then ${\displaystyle k\geq K_{\epsilon }}$ and ${\displaystyle n_{k}\geq k\geq N_{\epsilon }}$. Therefore for any ${\displaystyle n\geq N_{\epsilon }}$, we obtain

${\displaystyle \left|x_{n}-a\right|=\left|\left(x_{n}-x_{n_{k}}\right)+\left(x_{n_{k}}-a\right)\right|\leq \left|x_{n}-x_{n_{k}}\right|+\left|x_{n_{k}}-a\right|<{\frac {\epsilon }{2}}+{\frac {\epsilon }{2}}=\epsilon }$

Thus the entire sequence ${\displaystyle \left\{x_{n}\right\}}$ converges to ${\displaystyle a}$.

quod erat demonstrandum

## Limit Points

A limit point of a sequence ${\displaystyle \left\{x_{n}\right\}}$ is the limit of any convergent subsequence of ${\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 ${\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 ${\displaystyle \left[a,b\right]}$, then all its limits belong to ${\displaystyle \left[a,b\right]}$ as well (by comparison theorem)
• The set of limit points of the sequence ${\displaystyle \left\{\sin {n}\right\}}$ is the entire interval ${\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.