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

$\underset{n\to \mathrm{\infty }}{\lim }\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 \mathrm{\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{\mathbb{N}}$. Hence the sequence $\left\{a^n\right\}$ is strictly decreasing and bounded. Therefore it converges to some $x\in \mathbb{ℝ}$.

Since $a^{n+1}=a^{n}a$ for all $n$, it follows that $a^{n+1}\to xa$ as $n\to \mathrm{\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 $xa=x$, which implies that $x=0$.

quod erat demonstrandum

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

Proof. Since $a>1$, it follows that $a^{n+1}>a^n>1$ for all $n\in \mathbb{\mathbb{N}}$. Hence $\left\{a^n\right\}$ is strictly increasing. Then $\left\{a^n\right\}$ either diverges to $+\mathrm{\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 $+\mathrm{\infty }$.

quod erat demonstrandum

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

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

Proof. If $a\ge 1$, then $a^{n+1}\ge a^n\ge 1$ for all $n\in \mathbb{\mathbb{N}}$, which implies that $\sqrt[n(n+1)]{a^{n+1}}\ge \sqrt[n(n+1)]{a^n}\ge 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}\ge \sqrt[n+1]{a}\ge 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}\ge \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={(1+\frac{1}{n})}^n$ for $n\in \mathbb{\mathbb{N}}$ is increasing and bounded, hence it is convergent.

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

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

$\begin{array}{rl}{x}_n& ={(1+\frac{1}{n})}^n\\ & ={\left(\frac{n+1}{n}\right)}^n\\ & =\frac{(n+1{)}^n}{n^n}\end{array}$

If $n\ge 2$, then similarly

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

Hence

$\begin{array}{rl}\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}\\ & ={(1-\frac{1}{n^2})}^{n-1}(1+\frac{1}{n})\end{array}$

To continue, we need the following lemma:

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

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

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

$\begin{array}{rl}(1-x{)}^{k+1}& ={(1+x)}^k(1-x)\\ & \ge (1-kx)(1-x)\\ & =1-kx-x+k{x}^2>1-(k+1)x\end{array}$

Thus the lemma holds by induction on $k$.

Remark. According to the binomial formula,

$(1-x{)}^k=1-kx+\frac{k(k-1)}{2}{x}^2-\dots$

Using this lemma, we obtain that

$\begin{array}{rl}\frac{x_n}{x_{n-1}}& ={(1-\frac{1}{n^2})}^{n-1}(1+\frac{1}{n})\\ & \ge (1-\frac{n-1}{n^2})(1+\frac{1}{n})\\ & =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{array}$

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{array}{rl}{x}_n& ={(1+\frac{1}{n})}^n\\ & =\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k}){\left(\frac{1}{n}\right)}^k\\ & =\sum _{k=0}^n\frac{n!}{k!(n-k)!}{\left(\frac{1}{n}\right)}^k\\ \end{array}$

Observe that $\frac{n!}{k!(n-k)!}{\left(\frac{1}{n}\right)}^k\le 1$ for all $0\le k\le 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\le \sum _{k=0}^n\frac{1}{k!}=1+\frac{1}{1!}+\dots +\frac{1}{n!}$

Further observe that $k!\ge 2^{k-1}$ for all $k\ge 0$ because $1\cdot 2\cdot 3\dots k\ge 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{array}{rl}{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{array}$

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 $ϵ>0$, there exists $N\in \mathbb{\mathbb{N}}$ such that $|x_n-x_m|<ϵ$ whenever $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 $\left\{x_n\right\}$ be a convergent sequence and $a$ be its limit. Then for any $ϵ>0$ there exists $N\in \mathbb{\mathbb{N}}$ such that $|x_n-a|<\frac{ϵ}{2}$ whenever $n\ge N$. Now for any natural numbers $n,m\ge N$ we have

$|x_n-x_m|=|x_n-a+a-x_m|\le |x_n-a|+|x_m-a|<\frac{ϵ}{2}+\frac{ϵ}{2}=ϵ$

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{\mathbb{N}}$ such that $|x_n-x_m|<1$ whenever $n,m\ge N$. In particular, $|x_n-x_N|<1$ for all $n\ge N$. Then

$|x_n|=|(x_n-x_N)+x_N|\le |x_n-x_N|+|x_N|<|x_N|+1$

It follows that for any natural number $n$, we have $|x_n|\le M$, where $M=\max (|x_1|,|x_2|,\dots ,|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{\mathbb{N}}}$ converging to some $a\in \mathbb{ℝ}$. Given $ϵ>0$, there exists $K_{ϵ}\in \mathbb{\mathbb{N}}$ such that $|x_{n_k}-a|<\frac{ϵ}{2}$ for all $k\ge K_{ϵ}$. Also, there exists $N_{ϵ}\in \mathbb{\mathbb{N}}$ such that $|x_n-x_m|<\frac{ϵ}{2}$ whenever $n,m\ge N_{ϵ}$. Let $k=\max (K_{ϵ},N_{ϵ})$. Then $k\ge K_{ϵ}$ and $n_k\ge k\ge N_{ϵ}$. Therefore for any $n\ge N_{ϵ}$, we obtain

$|x_n-a|=|(x_n-x_{n_k})+(x_{n_k}-a)|\le |x_n-x_{n_k}|+|x_{n_k}-a|<\frac{ϵ}{2}+\frac{ϵ}{2}=ϵ$

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\{{(-1)}^n\right\}$ has 2 limit points, namely 1 and −1
• If all elements of a sequence belong to a closed interval $[a,b]$, then all its limits belong to $[a,b]$ as well (by comparison theorem)
• The set of limit points of the sequence $\{\sin n\}$ is the entire interval $[-1,1]$ (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.