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 $k!\geq 2^{k-1}$ for all $k\geq 0$ because $1\cdot 2\cdot 3\dots k\geq 2\cdot 2\dots 2$. There are $k-1$ factors greater than 2 on the LHS, and $k-1$ factors equal to 2 on the RHS.

Therefore we obtain

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

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

$|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 $n$, we have $|x_{n}|\leq M$, where $M=\max {(|x_{1}|,|x_{2}|,\ldots ,|x_{N-1}|,|x_{N}|+1)}$.

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

$\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 $\left\{x_{n}\right\}$ converges to $a$.

quod erat demonstrandum

Limit Points

A limit point of a sequence $\left\{x_{n}\right\}$ is the limit of any convergent subsequence of $\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 $\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 $\left[a,b\right]$, then all its limits belong to $\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 $\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.