Exercises: Convergence and divergence – "Math for Non-Geeks"

Proving convergence of a sequence

Exercise (Convergence of a sequence 1)

Use the epsilon-definition to prove that the sequence $\left({\frac {2}{n^{2}}}\right)_{n\in \mathbb {N} }$ converges. What is its limit?

How to get to the proof? (Convergence of a sequence 1)

How does this sequence behave for large $n$ ? The denominator stays constant at $2$ , while the enumerator $n^{2}$ grows towards infinity. So the fraction ${\frac {2}{n^{2}}}$ should go to $0$ .

Now, let us prove this. The definition of the limit for this sequence reads:

$\forall \epsilon >0\,\exists N\in \mathbb {N} \,\forall n\geq N:\left|{\frac {2}{n^{2}}}-0\right|={\frac {2}{n^{2}}}<\epsilon$

Now,

${\begin{aligned}&{\frac {2}{n^{2}}}<\epsilon \\[0.3em]\iff &2<n^{2}\epsilon \\[0.3em]\iff &{\frac {2}{\epsilon }}<n^{2}\\[0.3em]\iff &n>{\sqrt {\frac {2}{\epsilon }}}\end{aligned}}$

The Archimedean Axiom allows to find an $N\in \mathbb {N}$ with $N>{\sqrt {\tfrac {2}{\epsilon }}}$ . By the above inequalities, for all sequence elements with $n\geq N$ , there is ${\tfrac {2}{n^{2}}}<\epsilon$ . So the sequence converges to 0.

Solution (Convergence of a sequence 1)

Let $\epsilon >0$ . We choose an $N\in \mathbb {N}$ with $N>{\sqrt {\tfrac {2}{\epsilon }}}$ . This is possible by the Archimedean axiom. Then, for all $n\geq N$ there is

${\begin{aligned}\left|{\tfrac {2}{n^{2}}}-0\right|&={\tfrac {2}{n^{2}}}\\&\leq {\tfrac {2}{N^{2}}}\\&<\epsilon .\end{aligned}}$

Exercise (Convergence of a sequence 2)

Use the epsilon-definition to show that the sequence $\left({\frac {{\sqrt {n}}-1}{{\sqrt {n}}+1}}\right)_{n\in \mathbb {N} }$ converges to $1$ .

How to get to the proof? (Convergence of a sequence 2)

For the epsilon-definition, we need to verify: $\forall \epsilon >0\,\exists N\in \mathbb {N} \,\forall n\geq N:\left|{\frac {{\sqrt {n}}-1}{{\sqrt {n}}+1}}-1\right|<\epsilon$ This means, for each $\epsilon$ , we need to find a suitable $N$ , such that for $\left|{\frac {{\sqrt {n}}-1}{{\sqrt {n}}+1}}-1\right|<\epsilon$ holds after the sequence has passed element number $N$ . So let us find such an $N$ by re-shaping the condition: ${\begin{aligned}\left|{\frac {{\sqrt {n}}-1}{{\sqrt {n}}+1}}-1\right|<\epsilon &\Leftrightarrow \left|{\frac {{\sqrt {n}}-1-{\sqrt {n}}-1}{{\sqrt {n}}+1}}\right|<\epsilon \\&\Leftrightarrow \left|{\frac {-2}{{\sqrt {n}}+1}}\right|<\epsilon \\&\Leftrightarrow {\frac {2}{{\sqrt {n}}+1}}<\epsilon \\&\Leftrightarrow {\sqrt {n}}+1>{\frac {2}{\epsilon }}\\&\Leftrightarrow {\sqrt {n}}>{\frac {2}{\epsilon }}-1\\&\Leftrightarrow n>\left({\frac {2}{\epsilon }}-1\right)^{2}\end{aligned}}$ That means, we need an $N\in \mathbb {N}$ with $N>\left({\frac {2}{\epsilon }}-1\right)^{2}$ . This exists by the Archimedean axiom and we are done with the proof.

Solution (Convergence of a sequence 2)

Let $\epsilon >0$ . We choose an $N\in \mathbb {N}$ with $N>\left({\tfrac {2}{\epsilon }}-1\right)^{2}$ . This can be done by the Archimedean axiom. Then, for all $n\geq N$ there is

${\begin{aligned}\left|{\tfrac {{\sqrt {n}}-1}{{\sqrt {n}}+1}}-1\right|&=\left|{\tfrac {-2}{{\sqrt {n}}+1}}\right|\\&={\tfrac {2}{{\sqrt {n}}+1}}\\&\leq {\tfrac {2}{{\sqrt {N}}+1}}\\&<\epsilon .\end{aligned}}$

Proving divergence for an alternating sequence

Exercise (Divergence of an alternating sequence)

Prove that the sequence $((-1)^{n})_{n\in \mathbb {N} }$ diverges.

How to get to the proof? (Divergence of an alternating sequence)

We need to show that $\forall a\in \mathbb {R} \,\exists \epsilon >0\,\forall N\in \mathbb {N} \,\exists n\geq N:|(-1)^{n}-a|\geq \epsilon$ Intuitively, as the sequence alternates between $1$ and $-1$ , the only possible limits are $a=-1$ and $a=1$ . However, we have to show the above statement for all $a\in \mathbb {R}$ in order to prove divergence.

First, let us consider the case $a<0$ : For all even $n\in \mathbb {N}$ there is $(-1)^{n}-a=1-a\geq 1$ , so $|(-1)^{n}-a|=|1-a|\geq 1$ That means, we are further away from $a$ than $\epsilon =1$ . For any $N\in \mathbb {N}$ there will be an even $n\in \mathbb {N}$ with $n\geq N$ , such that $|(-1)^{n}-a|\geq 1\geq \epsilon$

Analogously, for $a\geq 0$ and all odd $n\in \mathbb {N}$ : $|(-1)^{n}-a|=|-1-a|\geq 1$ So if we choose again $\epsilon =1$ , then for each $N\in \mathbb {N}$ there will be an odd $n\in \mathbb {N}$ with $n\geq N$ , such that $|(-1)^{n}-a|\geq 1\geq \epsilon$ I.e. for all $a\in \mathbb {R}$ , the sequence has infinitely many elements staying away by more than 1 from $a$ and hence, the sequence diverges.

Proof (Divergence of an alternating sequence)

Case 1: Let $a<0$ . Choose $\epsilon =1$ and $N\in \mathbb {N}$ arbitrary. Now, take an even $n$ with $n\geq N$ . Then, $|(-1)^{n}-a|=|1-a|\geq 1$ Case 2: Let $a\geq 0$ . Choose $\epsilon =1$ and $N\in \mathbb {N}$ arbitrary. Now, take an odd $n$ with $n\geq N$ . Then, $|(-1)^{n}-a|=|-1-a|\geq 1$

Proof (Alternative proof by contradiction)

For two subsequence elements $a_{n}$ and $a_{n+1}$ there is always $|a_{n}-a_{n+1}|=|(-1)^{n}-(-1)^{n+1}|=|\pm 2|=2.$ . So if for $\epsilon =1>0$ there was an $N\in \mathbb {N}$ and an $a\in \mathbb {R}$ with $|(-1)^{n}-a|<\epsilon \ \forall n\geq N$ then, we would have $2=|(-1)^{N}-(-1)^{N+1}|=|(-1)^{N}-a+a-(-1)^{N+1}|{\underset {\text{inequality}}{\overset {\text{triangle-}}{\leq }}}|(-1)^{N}-a|+|a-(-1)^{N+1}|=|(-1)^{N}-a|+|(-1)^{N}-a|<\epsilon +\epsilon =1+1=2$

Powers of sequences

Exercise (Powers of sequences)

For any power $k\in \mathbb {N}$ and a given sequence $(a_{n})_{n\in \mathbb {N} }$ converging as $\lim _{n\to \infty }a_{n}=a$ the $k$ -th power of this sequence will also converge to $\lim _{n\to \infty }a_{n}^{k}=a^{k}$ . Prove this statement directly, using the epsilon-definition (without the product rule).

How to get to the proof? (Powers of sequences)

We need to show that

$|a_{n}^{k}-a^{k}|$

will fall below any $\epsilon >0$ . What we can use is that $|a_{n}-a|$ gets arbitrarily small. It is therefore useful, to get a factor of $|a_{n}-a|$ out of the term $|a_{n}^{k}-a^{k}|$ . This is done by using

$x^{k}-y^{k}=(x-y)(x^{k-1}y^{0}+x^{k-2}y^{1}+x^{k-3}y^{2}+\ldots +x^{2}y^{k-3}+x^{1}y^{k-2}+x^{0}y^{k-1})=(x-y)\sum _{j=0}x^{k-1-j}y^{j}$

We can prove this statement similar to the geometric sum formula:

${\begin{array}{lll}&\sum \limits _{j=0}^{k-1}x^{k-1-j}y^{j}&=\ x^{k-1}y^{0}+x^{k-2}y^{1}+\ldots +x^{1}y^{k-2}+x^{0}y^{k-1}\\[0.5em]&&{\color {OliveGreen}\left\downarrow \ {\text{multiply both sides with }}y\right.}\\[0.5em]\Rightarrow \ &y\sum \limits _{j=0}^{k-1}x^{k-1-j}y^{j}&=\ x^{k-1}y^{1}+x^{k-2}y^{2}+\ldots +x^{1}y^{k-1}+x^{0}y^{k}\\[0.5em]&&{\color {OliveGreen}\left\downarrow \ {\text{multiply with x and subtract both expressions}}\right.}\\[0.5em]\Rightarrow \ &x\sum \limits _{j=0}^{k-1}x^{k-1-j}y^{j}-y\sum \limits _{j=0}^{k-1}x^{k-1-j}y^{j}&=\ (x^{k}y^{0}+x^{k-1}y^{1}+\ldots +x^{2}y^{k-2}+x^{1}y^{k-1})-(x^{k-1}y^{1}+x^{k-2}y^{2}\ldots +x^{1}y^{k-1}+x^{0}y^{k})=x^{k}-y^{k}\\[0.5em]&&{\color {OliveGreen}\left\downarrow \ {\text{factor out }}\sum \limits _{j=0}^{k-1}x^{k-1-j}y^{j}\right.}\\[0.5em]\Rightarrow \ &(x-y)\cdot \sum \limits _{j=0}^{k-1}x^{k-1-j}y^{j}&=\ x^{k}-y^{k}\\[0.5em]&&{\color {OliveGreen}\left\downarrow \ {}\cdot {\frac {1}{x-y}}\right.}\\[0.5em]\Rightarrow \ &\sum \limits _{j=0}^{k-1}x^{k-1-j}y^{j}&=\ {\frac {x^{k}-y^{k}}{x-y}}\\[0.5em]\end{array}}$

We use this auxiliary formula with $x=a_{n}$ and $y=a$ :

$|a_{n}^{k}-a^{k}|=|(a_{n}-a)\sum \limits _{j=0}^{k-1}a_{n}^{k-1-j}a^{j}|=|(a_{n}-a)|\cdot |\sum \limits _{j=0}^{k-1}a_{n}^{k-1-j}a^{j}|$

The first factor of $|a_{n}-a|$ is nice, since we can control it. The second factor will be bounded by the triangle inequality $|\sum \limits _{k=1}^{n}a_{k}|\leq \sum _{k=1}^{n}|a_{k}|$ and we get

$|a_{n}^{k}-a^{k}|\leq |(a_{n}-a)|\cdot \sum \limits _{j=0}^{k-1}|a_{n}|^{k-1-j}|a|^{j}$

If we can now show that the second factor $\sum \limits _{j=0}^{k-1}|a_{n}|^{k-1-j}|a|^{j}$ is bounded from above by a constant, then $|a_{n}^{k}-a^{k}|$ gets arbitrarily small and we are done. Now, we know that $(a_{n})$ converges, so it is bounded. We call this bound $M>0$ with $|a_{n}|\leq M$ for all $n\in \mathbb {N}$ . Therefore, $\sum \limits _{j=0}^{k-1}|a_{n}|^{k-1-j}|a|^{j}\leq \sum \limits _{j=0}^{k-1}M^{k-1-j}|a|^{j}=C<\infty$ .

Therefore, $|a_{n}^{k}-a^{k}|$ gets arbitrarily small (below any $\epsilon >0$ ) and we have convergence $\lim _{n\to \infty }a_{n}^{k}=a^{k}$ .

Proof (Powers of sequences)

Let $\epsilon >0$ be arbitrary. Since $(a_{n})$ converges, there must be an $M>0$ with $|a_{n}|\leq M$ for all $n\in \mathbb {N}$ . Since $\lim _{n\rightarrow \infty }a_{n}=a$ there is an $N\in \mathbb {N}$ with $|a_{n}-a|<{\tfrac {\epsilon }{C}}$ for all $n\geq N$ , where we define the constant $C=\sum \limits _{j=0}^{k-1}M^{k-1-j}|a|^{j}$ . Let now $n\geq N$ be arbitrary. Then

${\begin{aligned}|a_{n}^{k}-a^{k}|&{\underset {\text{formula}}{\overset {\text{auxiliary}}{=}}}|a_{n}-a|\cdot |\sum \limits _{j=0}^{k-1}a_{n}^{k-1-j}a^{j}|\\&\quad {\color {Gray}\left\downarrow \ {\text{triangle inequality}}\right.}\\&\leq |a_{n}-a|\cdot \sum \limits _{j=0}^{k-1}|a_{n}|^{k-1-j}|a|^{j}\\&\quad {\color {Gray}\left\downarrow \ (a_{n})\ {\text{bounded}}\right.}\\&\leq |a_{n}-a|\cdot \underbrace {\sum \limits _{j=0}^{k-1}M^{k-1-j}|a|^{j}} _{=C}\\&<{\tfrac {\epsilon }{C}}\cdot C\\&=\epsilon \end{aligned}}$

Limit theorems

Exercise (Limits of sequences)

Investigate, whether $(a_{n})_{n\in \mathbb {N} }$ , $(b_{n})_{n\in \mathbb {N} }$ , $(c_{n})_{n\in \mathbb {N} }$ , $(d_{n})_{n\in \mathbb {N} }$ , $(e_{n})_{n\in \mathbb {N} }$ and $(f_{n})_{n\in \mathbb {N} }$ converge. Determine the limit in the respective case.

$a_{n}={\frac {{\sqrt[{n}]{n^{3}}}+{\sqrt[{n}]{3}}}{3{\sqrt[{n}]{n}}+{\sqrt[{n}]{3n}}}}$
$b_{n}={\frac {2n^{3}+n^{2}+3}{n^{3}-4}}$
$c_{n}={\frac {(n+2)^{2}-n^{2}}{3n}}$
$d_{n}={\sqrt {n+1}}-{\sqrt {n}}$
$e_{n}={\frac {{\sqrt {n^{2}+1}}+n}{3n+2}}$
$f_{n}={\frac {1+2+\ldots +n}{n^{2}}}$

Solution (Limits of sequences)

1. The trick is to split the roots ${\sqrt[{n}]{n^{3}}}$ and ${\sqrt[{n}]{3n}}$ in factors ${\sqrt[{n}]{3}}$ and ${\sqrt[{n}]{n}}$ . We can then use that $\lim _{n\to \infty }{\sqrt[{n}]{3}}=1$ and $\lim _{n\to \infty }{\sqrt[{n}]{n}}=1$ and patch them together, using the limit theorems:

$a_{n}={\frac {{\sqrt[{n}]{n^{3}}}+{\sqrt[{n}]{3}}}{3{\sqrt[{n}]{n}}+{\sqrt[{n}]{3n}}}}={\frac {{\sqrt[{n}]{n}}\cdot {\sqrt[{n}]{n}}\cdot {\sqrt[{n}]{n}}+{\sqrt[{n}]{3}}}{3{\sqrt[{n}]{n}}+{\sqrt[{n}]{3}}\cdot {\sqrt[{n}]{n}}}}{\underset {\text{theorems}}{\overset {\text{limit-}}{\to }}}{\frac {1\cdot 1\cdot 1+1}{3\cdot 1+1\cdot 1}}={\frac {2}{4}}={\frac {1}{2}}$

2. For fractions of polynomials, the "polynomial with highest degree" usually wins. We have two polynomials of equal degree 3. In that case, one has a finite limit. we can determine it by factoring out the highest power and using the limit theorems.

$b_{n}={\frac {2n^{3}+n^{2}+3}{n^{3}-4}}={\frac {n^{3}\cdot (2+{\frac {1}{n}}+{\frac {3}{n^{3}}})}{n^{3}\cdot (1-{\frac {4}{n^{3}}})}}={\frac {2+{\frac {1}{n}}+{\frac {3}{n^{3}}}}{1-{\frac {4}{n^{3}}}}}{\underset {\text{theorems}}{\overset {\text{limit-}}{\to }}}{\frac {2+0+0}{1-0}}=2$

3. It looks as if the enumerator was of degree 2 and the denominator of degree 1, so one might think at first glance that the enumerator "wins" and we get divergence to infinity. However, there is a minus sign in the enumerator, so we need to do some simplification first. indeed, the $n^{2}$ -terms cancel and we get a finite limit:

$c_{n}={\frac {(n+2)^{2}-n^{2}}{3n}}={\frac {n^{2}+4n+4-n^{2}}{3n}}={\frac {4n+4}{3n}}={\frac {4+{\frac {4}{n}}}{3}}{\underset {\text{theorems}}{\overset {\text{limit-}}{\to }}}{\frac {4+0}{3}}={\frac {4}{3}}$

4. What will happen for large $n$ ? At first glance, we go to $\infty -\infty$ which is no determinate result. but after some simplifications:

$d_{n}={\sqrt {n+1}}-{\sqrt {n}}={\frac {({\sqrt {n+1}}-{\sqrt {n}})({\sqrt {n+1}}+{\sqrt {n}})}{{\sqrt {n+1}}+{\sqrt {n}}}}={\frac {n+1-n}{{\sqrt {n+1}}+{\sqrt {n}}}}={\frac {1}{{\sqrt {n+1}}+{\sqrt {n}}}}={\frac {\frac {1}{\sqrt {n}}}{{\sqrt {1+{\frac {1}{n}}}}+1}}{\underset {\text{theorems}}{\overset {\text{limit-}}{\to }}}{\frac {0}{{\sqrt {1+0}}+1}}=0$

Alternative solution: (squeeze theorem)

$\underbrace {0} _{=b_{n}}\leq \underbrace {{\sqrt {n+1}}-{\sqrt {n}}} _{=d_{n}}={\tfrac {({\sqrt {n+1}}-{\sqrt {n}})({\sqrt {n+1}}+{\sqrt {n}})}{{\sqrt {n+1}}+{\sqrt {n}}}}={\tfrac {n+1-n}{{\sqrt {n+1}}+{\sqrt {n}}}}={\tfrac {1}{{\sqrt {n+1}}+{\sqrt {n}}}}\leq \underbrace {\tfrac {1}{\sqrt {n}}} _{=c_{n}}$ There is $\lim _{n\to \infty }b_{n}=0=\lim _{n\to \infty }c_{n}$ . The squeeze theorem hence yields $\lim _{n\to \infty }d_{n}=0$ .

5. Again a square root. For large $n$ , there will be ${\sqrt {n^{2}+1}}\approx n$ So both enumerator and denominator behave like a polynomial of degree 1. We factor out an $n$ and obtain a finite limit:

$e_{n}={\frac {{\sqrt {n^{2}+1}}+n}{3n+2}}={\frac {{\sqrt {1+{\frac {1}{n^{2}}}}}+1}{3+{\frac {2}{n}}}}{\underset {\text{theorems}}{\overset {\text{limit-}}{\to }}}{\frac {{\sqrt {1+0}}+1}{3+0}}={\frac {2}{3}}$

6. The long sum can be simplified using Gauss' sum formula $1+2+\ldots +n={\tfrac {n(n+1)}{2}}$ . Then, we get two polynomials of degree 2, where we can factor out an $n^{2}$ :

$f_{n}={\frac {1+2+\ldots +n}{n^{2}}}{\underset {\text{sum formula}}{\overset {\text{arithmetic}}{=}}}{\frac {\frac {n(n+1)}{2}}{n^{2}}}={\frac {n^{2}+n}{2n^{2}}}={\frac {1+{\frac {1}{n}}}{2}}{\underset {\text{theorems}}{\overset {\text{limit-}}{\to }}}{\frac {1+0}{2}}={\frac {1}{2}}$

Warning

It is tempting to think: " $1+2+\ldots +n$ is a polynomial of degree 1" and to factor out an $n$ . This will not yield the desired result, as the number of summands in this polynomial depends in $n$ . If you have a sum whose number of elements increases in $n$ , you must always resolve the sum first into some expression with a finite amount of terms! There are cases in which you have sums, where each summand goes to 0, but you get $\infty$ -many summands, so the limit is not necessarily 0.

Exercise (Sequences depending on a parameter)

Investigate whether $(a_{n})_{n\in \mathbb {N} }$ with $a_{n}={\frac {n+z^{n}}{n-z^{n}}}$ converges, depending on the parameter $z\in \mathbb {R}$ .

How to get to the proof? (Sequences depending on a parameter)

The result will depend on whether $|z|\leq 1$ or $|z|>1$ . In case $|z|\leq 1$ , $z^{n}$ will stay bounded and $n$ dominates both the enumerator and the denominator. In case $|z|>1$ , $z^{n}$ grows exponentially and hence dominates the fraction.

Proof (Sequences depending on a parameter)

Case 1: For $|z|\leq 1$ there is $\lim _{n\to \infty }{\frac {n+z^{n}}{n-z^{n}}}=\lim _{n\to \infty }{\frac {1+{\frac {z^{n}}{n}}}{1-{\frac {z^{n}}{n}}}}{\underset {\text{theorems}}{\overset {\text{limit-}}{=}}}{\frac {1+0}{1-0}}=1$ since $\lim _{n\to \infty }{\frac {z^{n}}{n}}=0$ .

Case 2: For $|z|>1$ there is $\lim _{n\to \infty }{\frac {n+z^{n}}{n-z^{n}}}=\lim _{n\to \infty }{\frac {{\frac {n}{z^{n}}}+1}{{\frac {n}{z^{n}}}-1}}{\underset {\text{theorems}}{\overset {\text{limit-}}{=}}}{\frac {0+1}{0-1}}=-1$ since $\lim _{n\to \infty }{\frac {n}{z^{n}}}=0$ .

Exponential sequences

Exercise (Exponential sequences)

Investigate the following sequences $(a_{n})_{n\in \mathbb {N} }$ , $(b_{n})_{n\in \mathbb {N} }$ , $(c_{n})_{n\in \mathbb {N} }$ and $(d_{n})_{n\in \mathbb {N} }$ for converges. If they converge, determine the limit.

$a_{n}=\left(1+{\frac {1}{n}}\right)^{2n}$
$b_{n}=\left(1+{\frac {1}{n}}\right)^{n+2}$
$c_{n}=\left(1+{\frac {1}{n+2}}\right)^{n}$
$d_{n}=\left(1-{\frac {1}{n}}\right)^{n}$

Solution (Exponential sequences)

1.We make use of $\left(1+{\frac {1}{n}}\right)^{n}\to e$ : $\lim _{n\to \infty }a_{n}=\lim _{n\to \infty }\left(1+{\frac {1}{n}}\right)^{2n}=\lim _{n\to \infty }\left[\left(1+{\frac {1}{n}}\right)^{n}\right]^{2}{\underset {\text{theorems}}{\overset {\text{limit-}}{=}}}\left[\lim _{n\to \infty }\left(1+{\frac {1}{n}}\right)^{n}\right]^{2}=e^{2}$

2. As above, by $\left(1+{\frac {1}{n}}\right)^{n}\to e$ : $\lim _{n\to \infty }b_{n}=\lim _{n\to \infty }\left(1+{\frac {1}{n}}\right)^{n+2}=\lim _{n\to \infty }\left(1+{\frac {1}{n}}\right)^{n}\left(1+{\frac {1}{n}}\right)^{2}{\underset {\text{theorems}}{\overset {\text{limit-}}{=}}}\lim _{n\to \infty }\left(1+{\frac {1}{n}}\right)^{n}\cdot \lim _{n\to \infty }\left(1+{\frac {1}{n}}\right)^{2}=e\cdot (1+0)^{2}=e$

3. This case requires a little index shift ${\begin{aligned}\lim _{n\to \infty }c_{n}&=\lim _{n\to \infty }\left(1+{\frac {1}{n+2}}\right)^{n}=\lim _{n\to \infty }\left(1+{\frac {1}{n+2}}\right)^{n+2-2}=\lim _{n\to \infty }\left(1+{\frac {1}{n+2}}\right)^{n+2}\left(1+{\frac {1}{n+2}}\right)^{-2}\\&{\underset {\text{theorems}}{\overset {\text{limit-}}{=}}}\lim _{n\to \infty }\left(1+{\frac {1}{n+2}}\right)^{n+2}\cdot \lim _{n\to \infty }\left(1+{\frac {1}{n+2}}\right)^{-2}=e\cdot (1+0)^{-2}=e\end{aligned}}$

4. In order to apply $\left(1+{\frac {1}{n}}\right)^{n}\to e$ , we will extend both the enumerator and the denominator by $\left(1+{\frac {1}{n}}\right)$

$d_{n}=\left(1-{\frac {1}{n}}\right)^{n}=\left({\frac {n-1}{n}}\right)^{n}{\overset {n\geq 2}{=}}{\frac {1}{\left({\frac {n}{n-1}}\right)^{n}}}={\frac {1}{\left({\frac {n-1+1}{n-1}}\right)^{n}}}={\frac {1}{\left(1+{\frac {1}{n-1}}\right)^{n}}}{\underset {\text{theorems}}{\overset {\text{limit-}}{\to }}}{\frac {1}{e}}$ da $\lim _{n\to \infty }\left(1+{\tfrac {1}{n}}\right)^{n+1}=\lim _{n\to \infty }\left(1+{\tfrac {1}{n-1}}\right)^{n}=e$

Alternative solution: If we already know that $\lim _{n\to \infty }\left(1-{\tfrac {1}{n^{2}}}\right)^{n}=1$ , then we directly get

$c_{n}=\left(1-{\frac {1}{n}}\right)^{n}={\frac {\left(1-{\frac {1}{n}}\right)^{n}\left(1+{\frac {1}{n}}\right)^{n}}{\left(1+{\frac {1}{n}}\right)^{n}}}={\frac {\left(1-{\frac {1}{n^{2}}}\right)^{n}}{\left(1+{\frac {1}{n}}\right)^{n}}}={\underset {\text{theorems}}{\overset {\text{limit-}}{\to }}}{\frac {1}{e}}$

Squeeze theorem

Exercise (Squeeze theorem)

Determine the limit of the following sequences $(a_{n})_{n\in \mathbb {N} }$ :

$a_{n}={\tfrac {(-1)^{n}}{n^{k}}}$ for $k\in \mathbb {N}$
$a_{n}={\tfrac {n^{n}}{2^{n^{2}}}}$
$a_{n}={\sqrt[{n}]{n^{s}}}$ for $s\in \mathbb {Q} ^{+}$
$a_{n}={\sqrt[{n}]{\alpha x^{n}+\beta y^{n}}}$ for $\alpha ,\beta ,x,y\geq 0$
$a_{n}={\tfrac {1}{n}}\sum _{k=1}^{n}{\tfrac {k^{3}+n^{2}}{n^{3}+k^{2}}}$
$a_{n}=\left(1-{\tfrac {1}{n^{4}}}\right)^{n}$

Solution (Squeeze theorem)

1. For $k\in \mathbb {N}$ we have the upper and lower bound $\underbrace {-{\frac {1}{n}}} _{=b_{n}}\leq \underbrace {\frac {(-1)^{n}}{n^{k}}} _{=a_{n}}\leq \underbrace {\frac {1}{n}} _{=c_{n}}$ both tend to $\lim _{n\to \infty }b_{n}=0=\lim _{n\to \infty }c_{n}$ . The squeeze theorem now implies $\lim _{n\to \infty }a_{n}=\lim _{n\to \infty }{\tfrac {(-1)^{n}}{n^{k}}}=0$ .

2. For $n\geq 4$ there is $2^{n}\geq n^{2}$ , which gives an upper bound. For the lower bound, we just use 0: $\underbrace {0} _{=b_{n}}\leq \underbrace {\frac {n^{n}}{2^{n^{2}}}} _{=a_{n}}={\frac {n^{n}}{2^{n\cdot n}}}={\frac {n^{n}}{(2^{n})^{n}}}=\left({\frac {n}{2^{n}}}\right)^{n}\leq \left({\frac {n}{n^{2}}}\right)^{n}=\left({\frac {1}{n}}\right)^{n}={\frac {1}{n^{n}}}\leq \underbrace {\frac {1}{n}} _{=c_{n}}$ Since $\lim _{n\to \infty }b_{n}=0=\lim _{n\to \infty }c_{n}$ the squeeze theorem renders $\lim _{n\to \infty }a_{n}=\lim _{n\to \infty }{\tfrac {n^{n}}{2^{n^{2}}}}=0$ .

3. For $s\in \mathbb {Q} ^{+}$ we can find some $k\in \mathbb {N}$ with $k-1\leq s\leq k$ , i.e. we bound $s$ by the next smaller or bigger natural number. Since the root is monotone, we have as an upper or lower bound:

$\underbrace {\sqrt[{n}]{n^{k-1}}} _{=b_{n}}\leq \underbrace {\sqrt[{n}]{n^{s}}} _{=a_{n}}\leq \underbrace {\sqrt[{n}]{n^{k}}} _{=c_{n}}$

The limit theorems now yield $\lim _{n\to \infty }b_{n}=\lim _{n\to \infty }{\sqrt[{n}]{n^{k-1}}}=\lim _{n\to \infty }({\sqrt[{n}]{n}})^{k-1}=1^{k-1}=1$ and $\lim _{n\to \infty }c_{n}=\lim _{n\to \infty }{\sqrt[{n}]{n^{k}}}=\lim _{n\to \infty }({\sqrt[{n}]{n}})^{k}=1^{k}=1$ . So the original sequence is "squeezed" towards $\lim _{n\to \infty }a_{n}=1$ .

4. For $x\geq y$ , there is

$\underbrace {{\sqrt[{n}]{\alpha }}\cdot x} _{=b_{n}}={\sqrt[{n}]{\alpha x^{n}}}\leq \underbrace {\sqrt[{n}]{\alpha x^{n}+y^{n}}} _{=a_{n}}\leq {\sqrt[{n}]{\alpha x^{n}+\beta x^{n}}}={\sqrt[{n}]{(\alpha +\beta )x^{n}}}={\sqrt[{n}]{\alpha +\beta }}\cdot {\sqrt[{n}]{x^{n}}}=\underbrace {{\sqrt[{n}]{\alpha +\beta }}\cdot x} _{=c_{n}}$

The limits of the bounding sequences are $\lim _{n\to \infty }b_{n}=\lim _{n\to \infty }{\sqrt[{n}]{\alpha }}\cdot x=1\cdot x$ and $\lim _{n\to \infty }c_{n}=\lim _{n\to \infty }{\sqrt[{n}]{\alpha +\beta }}\cdot x=1\cdot x=x$ . So by the squeeze theorem $\lim _{n\to \infty }a_{n}=x$ .

In case $y\geq x$ we analogously obtain $\lim _{n\to \infty }a_{n}=y$ .

Both cases can be concluded as $\lim _{n\to \infty }a_{n}=\lim _{n\to \infty }{\sqrt[{n}]{x^{n}+y^{n}}}=\max\{x,y\}$ .

5. The powers 2 in the enumerator and denominator become relatively small compared to the powers 3 and should hence not affect the convergence. We establish an upper and a lower bounding sequence by leaving them out

$\underbrace {{\frac {1}{n}}\sum _{k=1}^{n}{\frac {k^{3}}{n^{3}+n^{2}}}} _{=b_{n}}\leq \underbrace {{\frac {1}{n}}\sum _{k=1}^{n}{\frac {k^{3}+n^{2}}{n^{3}+k^{2}}}} _{=a_{n}}\leq \underbrace {{\frac {1}{n}}\sum _{k=1}^{n}{\frac {k^{3}+n^{2}}{n^{3}}}} _{=c_{n}}$

Those bounding sequences converge to

$\lim _{n\to \infty }b_{n}=\lim _{n\to \infty }{\frac {1}{n}}\sum _{k=1}^{n}{\frac {k^{3}}{n^{3}+n^{2}}}=\lim _{n\to \infty }{\frac {1}{n^{4}+n^{3}}}\sum _{k=1}^{n}k^{3}{\underset {\text{formula}}{\overset {\text{sum-}}{=}}}\lim _{n\to \infty }{\frac {1}{n^{4}+n^{3}}}\cdot {\frac {n^{2}(n+1)^{2}}{4}}=\lim _{n\to \infty }{\frac {n^{4}+2n^{3}+n^{2}}{4n^{4}+4n^{3}}}=\lim _{n\to \infty }{\frac {1+{\frac {2}{n}}+{\frac {1}{n^{2}}}}{4+{\frac {4}{n}}}}={\frac {1}{4}}$

and

${\begin{aligned}\lim _{n\to \infty }c_{n}&=\lim _{n\to \infty }{\frac {1}{n}}\sum _{k=1}^{n}{\frac {k^{3}+n^{2}}{n^{3}}}=\lim _{n\to \infty }{\frac {1}{n^{4}}}\left(\sum _{k=1}^{n}k^{3}+\sum _{k=1}^{n}n^{2}\right){\underset {\text{formula}}{\overset {\text{sum-}}{=}}}\lim _{n\to \infty }{\frac {1}{n^{4}}}\cdot \left({\frac {n^{2}(n+1)^{2}}{4}}+n\cdot n^{2}\right)\\&=\lim _{n\to \infty }\left({\frac {n^{4}+2n^{3}+2n^{2}}{4n^{4}}}+{\frac {n^{3}}{n^{4}}}\right)=\lim _{n\to \infty }{\frac {1+{\frac {2}{n}}+{\frac {1}{n^{2}}}}{4}}+\lim _{n\to \infty }{\frac {1}{n}}={\frac {1}{4}}+0={\frac {1}{4}}\end{aligned}}$

So by means of the squeeze theorem $\lim _{n\to \infty }a_{n}={\tfrac {1}{4}}$ .

6. There is

$\underbrace {1} _{=c_{n}}=1^{n}=(1-0)^{n}\geq \underbrace {\left(1-{\frac {1}{n^{4}}}\right)^{n}} _{=a_{n}}{\underset {\text{inequality}}{\overset {\text{Bernoulli's}}{\geq }}}1-n\cdot {\frac {1}{n^{4}}}=\underbrace {1-{\frac {1}{n^{3}}}} _{=b_{n}}$

Both bounds converge to

$\lim _{n\to \infty }b_{n}=1=\lim _{n\to \infty }c_{n}$

So by the squeeze theorem $\lim _{n\to \infty }a_{n}=1$ . This trick would also work, if we replaced 4 by any other natural number $k>1$ .

Exercise (Squeeze theorem for products of roots)

Prove that $\lim _{n\to \infty }{\sqrt {n}}({\sqrt[{n}]{n}}-1)=0$ .

Solution (Squeeze theorem for products of roots)

It is easy to see that the sequence elements are greater than 0. So we need an upper bounding sequence for $|{\sqrt {n}}({\sqrt[{n}]{n}}-1)|={\sqrt {n}}({\sqrt[{n}]{n}}-1)$ which converges to 0. That means, we have to show that $({\sqrt[{n}]{n}}-1)$ goes to 0 fast enough. More explicitly, we need that $({\sqrt[{n}]{n}}-1)^{n}$ decreases as a sufficiently large power of $n$ . We consider $n\geq 4$ :

${\begin{aligned}n&=({\sqrt[{n}]{n}})^{n}\\[0.5em]&=(({\sqrt[{n}]{n}}-1)+1)^{n}\\[0.5em]&{\color {OliveGreen}\left\downarrow {\text{ binomial theorem}}\right.}\\[0.5em]&=\sum _{k=0}^{n}{\binom {n}{k}}({\sqrt[{n}]{n}}-1)^{k}\cdot \underbrace {1^{n-k}} _{=1}\\&=\underbrace {{\binom {n}{0}}({\sqrt[{n}]{n}}-1)^{0}} _{=1}+\underbrace {\sum _{k=1}^{2}{\binom {n}{k}}({\sqrt[{n}]{n}}-1)^{k}} _{\geq 0}+{\binom {n}{3}}({\sqrt[{n}]{n}}-1)^{3}+\underbrace {\sum _{k=4}^{n}{\binom {n}{k}}({\sqrt[{n}]{n}}-1)^{k}} _{\geq 0}\\[0.5em]&\geq 1+{\binom {n}{3}}({\sqrt[{n}]{n}}-1)^{3}\\[0.5em]&=1+{\frac {n(n-1)(n-2)}{6}}({\sqrt[{n}]{n}}-1)^{3}\end{aligned}}$

This implies

${\begin{aligned}n\geq 1+{\frac {n(n-1)(n-2)}{6}}\cdot ({\sqrt[{n}]{n}}-1)^{3}&\Leftrightarrow n-1\geq {\frac {n(n-1)(n-2)}{6}}\cdot ({\sqrt[{n}]{n}}-1)^{3}\\[0.5em]&\Leftrightarrow {\frac {6}{n(n-2)}}\geq ({\sqrt[{n}]{n}}-1)^{3}\\[0.5em]&\Leftrightarrow {\sqrt[{n}]{n}}-1\leq {\sqrt[{3}]{\frac {6}{n(n-2)}}}{\underset {n-2\geq {\tfrac {n}{2}}}{\overset {n\geq {\tfrac {n}{2}}}{\leq }}}{\sqrt[{3}]{\frac {6}{({\tfrac {n}{2}})^{2}}}}={\sqrt[{3}]{\frac {24}{n^{2}}}}\end{aligned}}$

We can replace the $({\sqrt[{n}]{n}}-1)$ by a sufficient power of $n$

$|{\sqrt {n}}({\sqrt[{n}]{n}}-1)-0|={\sqrt {n}}({\sqrt[{n}]{n}}-1)\leq {\sqrt {n}}{\sqrt[{3}]{\tfrac {24}{n^{2}}}}={\sqrt[{3}]{24}}\cdot {\frac {n^{\tfrac {1}{2}}}{n^{\tfrac {2}{3}}}}={\sqrt[{3}]{24}}\cdot {\frac {1}{n^{\tfrac {1}{6}}}}{\overset {n\to \infty }{\to }}0$

So there is also an upper bounding sequence converging to 0 and by the squeeze theorem $\lim _{n\to \infty }{\sqrt {n}}({\sqrt[{n}]{n}}-1)=0$ .

Monotonicity criterion and recursively defined sequences

Exercise (Monotonicity criterion)

Let $(b_{n})_{n\in \mathbb {N} }$ be a sequence with $0<b_{n}<1$ for all $n\in \mathbb {N}$ . Show, using the monotonicity criterion that in this case the product sequence $(a_{n})_{n\in \mathbb {N} }$ defined as

$a_{n}=\prod _{k=1}^{n}b_{k}=b_{1}\cdot b_{2}\cdot \ldots \cdot b_{n}$

converges.

Solution (Monotonicity criterion)

This can be seen as a recursively defined sequence with $a_{n+1}=a_{n}\cdot b_{n+1}$ , but one where we know the explicit form.

Step 1: $(a_{n})$ is monotonically decreasing, i.e. $a_{n+1}\leq a_{n}\iff {\tfrac {a_{n+1}}{a_{n}}}\leq 1$ $\forall n\in \mathbb {N}$ .

This is easy to see, as sequence elements tend to get smaller:

${\tfrac {a_{n+1}}{a_{n}}}={\frac {\prod _{k=1}^{n+1}b_{k}}{\prod _{k=1}^{n}b_{k}}}={\frac {\left(\prod _{k=1}^{n}b_{k}\right)\cdot b_{n+1}}{\prod _{k=1}^{n}b_{k}}}=b_{n+1}<1$

Step 2: $(a_{n})$ is bounded from below by $0$ , i.e $a_{n}\geq 0$ $\forall n\in \mathbb {N}$ .

This can be shown by induction in $n$ :

Induction basis: $n=1$ . $a_{1}=\prod _{k=1}^{1}b_{k}=b_{1}{\overset {\text{assumption}}{\geq }}0$ .

Induction step: $a_{n+1}=\prod _{k=1}^{n+1}b_{k}=\underbrace {\left(\prod _{k=1}^{n}b_{k}\right)} _{{\overset {\text{assumption}}{\geq }}0}\cdot \underbrace {b_{n+1}} _{\geq 0}\geq 0\cdot 0=0.$

Step 3: $(a_{n})$ actually converges.

This is a direct consequence of the monotonicity criterion: $(a_{n})$ is monotonically decreasing and bounded, so it converges.

Exercise (Convergence of a recursively defined sequence 1)

Why does the recursively defined sequence

$a_{0}=0,\ a_{n+1}={\frac {2}{3}}a_{n}+{\frac {1}{3}}$

converge? Determine its limit:

By finding an explicit form of the sequence
Using the monotonicity criterion

Solution (Convergence of a recursively defined sequence 1)

Part 1: Let us investigate the first sequence elements

${\begin{aligned}a_{0}&=0\\[0.3em]a_{1}&={\frac {2}{3}}a_{0}+{\frac {1}{3}}={\frac {2}{3}}\cdot 0+{\frac {1}{3}}={\frac {1}{3}}\\[0.3em]a_{2}&={\frac {2}{3}}a_{1}+{\frac {1}{3}}={\frac {2}{3}}\cdot {\frac {1}{3}}+{\frac {1}{3}}={\frac {2}{9}}+{\frac {3}{9}}={\frac {5}{9}}\\[0.3em]a_{3}&={\frac {2}{3}}a_{2}+{\frac {1}{3}}={\frac {2}{3}}\cdot {\frac {5}{9}}+{\frac {1}{3}}={\frac {10}{27}}+{\frac {9}{27}}={\frac {19}{27}}\\[0.3em]a_{4}&={\frac {2}{3}}a_{3}+{\frac {1}{3}}={\frac {2}{3}}\cdot {\frac {19}{27}}+{\frac {9}{27}}={\frac {38}{81}}+{\frac {27}{81}}={\frac {65}{81}}\\[0.3em]&\vdots \end{aligned}}$

Can we find a pattern? With a bit of training, one might see:

${\begin{aligned}a_{0}&=0\\[0.3em]a_{1}&={\frac {1}{3}}={\frac {3-2}{3}}={\frac {3^{1}-2^{1}}{3^{1}}}\\[0.3em]a_{2}&={\frac {5}{9}}={\frac {9-4}{9}}={\frac {3^{2}-2^{2}}{3^{2}}}\\[0.3em]a_{3}&={\frac {19}{27}}={\frac {27-8}{27}}={\frac {3^{3}-2^{3}}{3^{3}}}\\[0.3em]a_{4}&={\frac {65}{81}}={\frac {81-16}{81}}={\frac {3^{4}-2^{4}}{3^{4}}}\\[0.3em]&\vdots \end{aligned}}$

So we assert $a_{n}={\frac {3^{n}-2^{n}}{3^{n}}}$ for all $n\in \mathbb {N} _{0}$ . Let us prove the assertion by induction over $n$ :

Induction basis: $n=0$ . $a_{0}=0={\frac {3^{0}-2^{0}}{3^{0}}}$ .

Induction step: $a_{n+1}={\frac {2}{3}}a_{n}+{\frac {1}{3}}={\overset {\text{assumption}}{=}}{\frac {2}{3}}\cdot {\frac {3^{n}-2^{n}}{3^{n}}}+{\frac {1}{3}}={\frac {2\cdot (3^{n}-2^{n})+3^{n}}{3\cdot 3^{n}}}={\frac {2\cdot 3^{n}+2^{n+1}+3^{n}}{3^{n+1}}}={\frac {3^{n+1}-2^{n+1}}{3^{n+1}}}$

This verifies our assertion $a_{n}={\tfrac {3^{n}-2^{n}}{3^{n}}}$ for all $n\in \mathbb {N}$ (even though it was not easy to find). We can directly compute the limit of this expression using the limit theorems:

$\lim _{n\to \infty }a_{n}=\lim _{n\to \infty }{\frac {3^{n}-2^{n}}{3^{n}}}=\left[{\frac {3^{n}}{3^{n}}}-{\frac {2^{n}}{3^{n}}}\right]{\underset {\text{theorems}}{\overset {\text{limit}}{=}}}1-\lim _{n\to \infty }\left({\frac {2}{3}}\right)^{n}=1-0=1$

Part 2: is solved in 4 steps:

Step 1: $(a_{n})$ is monotonically increasing, i.e. $a_{n+1}\geq a_{n}$ $\forall n\in \mathbb {N} _{0}$ .

The proof runs by induction over $n$ :

Induction basis: $n=1$ . $a_{1}={\frac {2}{3}}\cdot a_{0}+{\frac {1}{3}}={\frac {2}{3}}\cdot 0+{\frac {1}{3}}={\frac {1}{3}}\geq 0=a_{0}$ .

Induction step: $a_{n+2}={\frac {2}{3}}a_{n+1}+{\frac {1}{3}}{\underset {a_{n+1}\geq a_{n}}{\overset {\text{assumption}}{\geq }}}{\frac {2}{3}}a_{n}+{\frac {1}{3}}=a_{n+1}$

Step 2: $(a_{n})$ is bounded from above by $1$ , i.e. $a_{n}\leq 1$ $\forall n\in \mathbb {N} _{0}$ .

This can also be shown inductively:

Induction basis: $n=0$ . $a_{0}=0\leq 1$ .

Induction step: $a_{n+1}={\frac {2}{3}}a_{n}+{\frac {1}{3}}{\underset {a_{n}\leq 1}{\overset {\text{assumption}}{\leq }}}{\frac {2}{3}}\cdot 1+{\frac {1}{3}}=1\leq 1$

Step 3: $(a_{n})$ converges.

As $(a_{n})$ is increasing and bounden, the monotonicity criterion can be applied and $(a_{n})$ converges.

Step 4: computing the limit.

An index shift will not affect the limit: $\lim _{n\to \infty }a_{n}=a=\lim _{n\to \infty }a_{n+1}$ . But plugging in the recursion formula into this equation and using the limit theorems , we will obtain the limit:

$\lim _{n\to \infty }a_{n}=a=\lim _{n\to \infty }a_{n+1}=\lim _{n\to \infty }{\frac {2}{3}}a_{n}+{\frac {1}{3}}={\frac {2}{3}}\cdot \left(\lim _{n\to \infty }a_{n}\right)+{\frac {1}{3}}={\frac {2}{3}}\cdot a+{\frac {1}{3}}$

We resolve for $a$ :

$a={\frac {2}{3}}a+{\frac {1}{3}}\Rightarrow {\frac {1}{3}}a={\frac {1}{3}}\Rightarrow a=1$

And the limit is $\lim _{n\to \infty }a_{n}=1$ (same as in part 1).

Exercise (convergence of a recursively defined sequence 2)

Let $a,b\in \mathbb {R}$ . Why does the recursively defined sequence

$a_{0}=a,\ a_{1}=b,\ a_{n+1}={\frac {2}{5}}a_{n}+{\frac {3}{5}}a_{n-1}$

converge? What is its limit?

Solution (convergence of a recursively defined sequence 2)

There is

${\begin{aligned}a_{n}-a_{n-1}&={\frac {2}{5}}a_{n-1}+{\frac {3}{5}}a_{n-2}-a_{n-1}\\&={\frac {3}{5}}a_{n-2}-{\frac {3}{5}}a_{n-1}\\&={\frac {3}{5}}(a_{n-2}-a_{n-1})\\&=-{\frac {3}{5}}(a_{n-1}-a_{n-2})\end{aligned}}$

We apply this step $n$ times and get

${\begin{aligned}a_{n}-a_{n-1}&=-{\frac {3}{5}}(a_{n-1}-a_{n-2})\\&=\left(-{\frac {3}{5}}\right)^{2}\left(a_{n-2}-a_{n-3}\right)\\&\ldots \\&=\left(-{\frac {3}{5}}\right)^{n-1}(a_{1}-a_{0})\\&=\left(-{\frac {3}{5}}\right)^{n-1}(b-a)\end{aligned}}$

So all differences $a_{n}-a_{n-1}$ are multiples of $(b-a)$ We obtain $a_{n}$ by adding up all differences (telescoping sum)

$\sum _{k=1}^{n}(a_{k}-a_{k-1})=a_{n}-a_{0}\iff a_{n}=a_{0}+\sum _{k=1}^{n}(a_{k}-a_{k-1})$

and get a geometric series:

$a_{n}=a_{0}+\sum _{k=1}^{n}\left(-{\frac {3}{5}}\right)^{k-1}(b-a)=a+(b-a)\sum _{k=0}^{n-1}\left(-{\frac {3}{5}}\right)^{k}=a+(b-a){\frac {1-(-{\frac {3}{5}})^{n}}{1-(-{\frac {3}{5}})}}=a+(b-a){\frac {1-(-{\frac {3}{5}})^{n}}{\frac {8}{5}}}=a+{\tfrac {5}{8}}(b-a)(1-(-{\tfrac {3}{5}})^{n})$

There is $\lim _{n\to \infty }(-{\tfrac {3}{5}})^{n}=0$ so the limit theorems yield

$\lim _{n\to \infty }a_{n}=\lim _{n\to \infty }a+{\tfrac {5}{8}}(b-a)(1-(-{\tfrac {3}{5}})^{n})=a+{\tfrac {5}{8}}(b-a)={\tfrac {3}{8}}a+{\tfrac {5}{8}}b$

Exercise (Monotonicity criterion for sequences)

Show the the sequence $(a_{n})_{n\in \mathbb {N} }$ defined by the recursion relation $a_{1}=1,\ a_{n+1}={\sqrt {1+a_{n}}}$ converges to the so-called golden ratio $g={\tfrac {1+{\sqrt {5}}}{2}}$ .

How to get to the proof? (Monotonicity criterion for sequences)

At first, we need a proof of convergence. Then, we can compute the limit. So first, let us show that $(a_{n})_{n\in \mathbb {N} }$ is monotone and bounded (then, the monotonicity criterion can be applied).

Why is it monotone? Let us compute the first sequence elements: $a_{1}=1,\ a_{2}={\sqrt {1+1}}={\sqrt {2}}\geq 1=a_{1},\ a_{3}={\sqrt {1+{\sqrt {2}}}}\geq {\sqrt {1+1}}={\sqrt {2}}=a_{2},\ a_{4}={\sqrt {1+{\sqrt {1+{\sqrt {2}}}}}}\geq {\sqrt {1+{\sqrt {1+1}}}}={\sqrt {1+{\sqrt {2}}}}=a_{3}$ We assert that $(a_{n})$ is monotonically increasing. Only a proof is required, e.g. by induction. Then, we need an upper bound. The limit of $(a_{n})$ shall be $g={\tfrac {1+{\sqrt {5}}}{2}}$ , so any number greater than $g$ will be an upper bound. Since $g={\tfrac {1+{\sqrt {5}}}{2}}\leq {\tfrac {1+{\sqrt {9}}}{2}}={\tfrac {1+3}{2}}={\tfrac {4}{2}}=2$ w simply choose $2$ as an upper bound for $(a_{n})$ . Of course, we need to verify that this is an upper bound by induction.

At this point, we have convergence of the sequence. Then, we need to show that $g$ is the limit and we are done.

Solution (Monotonicity criterion for sequences)

Step 1: $(a_{n})$ is monotonically increasing, i.e. $a_{n+1}\geq a_{n}$ $\forall n\in \mathbb {N}$ .

The proof is by induction over $n$ :

Induction basis: $n=1$ . $a_{2}={\sqrt {1+1}}={\sqrt {2}}\geq 1=a_{1}$ .

Induction step: $a_{n+2}={\sqrt {1+a_{n+1}}}{\underset {{\sqrt {.}}{\text{ is monotone}}}{\overset {\text{assumption:}}{\geq }}}{\sqrt {1+a_{n}}}=a_{n+1}$

Step 2: $(a_{n})$ is bounded from above by $2$ , i.e. $a_{n}\leq 2$ $\forall n\in \mathbb {N}$ .

The proof is again done by induction:

Induction basis: $n=1$ . $a_{1}=1\leq 2$ .

Induction step: $a_{n+1}={\sqrt {1+a_{n}}}{\underset {{\sqrt {.}}{\text{ is monotone}}}{\overset {\text{assumption:}}{\leq }}}{\sqrt {1+2}}={\sqrt {3}}\leq {\sqrt {4}}=2$

Note: We can also directly show $a_{n}\leq g$ by induction - if we first establish the equality $g^{2}=1+g$ .

Step 3: $(a_{n})$ converges.

$(a_{n})$ is monotonically increasing and bounded, so it converges by the monotonicity criterion.

Step 4: computing the limit.

An index shift will not change the limit: $\lim _{n\to \infty }a_{n}=a=\lim _{n\to \infty }a_{n+1}$ . We use the recursive definition, as well as the limit theorems and continuity of the root function $\lim _{n\to \infty }a_{n}=a=\lim _{n\to \infty }a_{n+1}=\lim _{n\to \infty }{\sqrt {1+a_{n}}}={\sqrt {1+\lim _{n\to \infty }a_{n}}}={\sqrt {1+a}}$ Now, we resolve $a={\sqrt {1+a}}$ for $a$ and obtain $a={\sqrt {1+a}}\Rightarrow a^{2}=1+a\Rightarrow a^{2}-a-1=0$ Which has two solutions: $x_{1,2}={\frac {1\pm {\sqrt {1+4}}}{2}}={\frac {1\pm {\sqrt {5}}}{2}}$ I.e. $a_{1}={\tfrac {1+{\sqrt {5}}}{2}}$ and $x_{2}={\tfrac {1-{\sqrt {5}}}{2}}$ . Which one is the limit? There is $x_{2}={\tfrac {1-{\sqrt {5}}}{2}}<0$ . Since $a_{1}=1$ and monotonicity, the limit of $(a_{n})$ can only be above $1$ . Hence, $x_{2}$ can not be the limit and we have convergence to $x_{1}$ .

So we have established convergence to $\lim _{n\to \infty }a_{n}={\tfrac {1+{\sqrt {5}}}{2}}=g$ .

Exercise (Monotonicity criterion for sequences)

Show that the sequence $(a_{n})_{n\in \mathbb {N} }$ , defined by $a_{1}=1,\ a_{n+1}=1+{\frac {1}{a_{n}}}$ converges to the golden ratio $g={\tfrac {1+{\sqrt {5}}}{2}}$ . Do this by showing

$1\leq a_{n}\leq 2$ for all $n\in \mathbb {N}$
The subsequence $(a_{2k-1})_{k\in \mathbb {N} }$ is monotonically increasing and the subsequence $(a_{2k})_{k\in \mathbb {N} }$ is monotonically decreasing.
Both subsequences converge to the same limit $g$ .

Solution (Monotonicity criterion for sequences)

Part 1: is done by induction over $n$ :

Induction basis: $n=1$ .

$1\leq a_{1}=1\leq 2$

Induction step: $1{\underset {\text{assumption}}{\overset {\text{induction}}{\leq }}}1+\underbrace {\frac {1}{a_{n}}} _{0\leq \ldots \leq 1}=a_{n+1}={\underset {\text{assumption}}{\overset {\text{induction}}{\leq }}}1+1=2$

Part 2: is also done by induction over $n$ :

At first, we show that the odd elements are monotonically increasing, i.e. $a_{2k+1}\geq a_{2k-1}$ for all $k\in \mathbb {N}$ .

Induction basis: $k=1$ .

$a_{3}=1+{\frac {1}{a_{2}}}=1+{\frac {1}{1+{\frac {1}{a_{1}}}}}=1+{\frac {1}{1+{\frac {1}{1}}}}=1+{\frac {1}{2}}={\frac {3}{2}}\geq 1=a_{1}$

Induction step: $a_{2k+3}=1+{\frac {1}{a_{2k+2}}}=1+{\frac {1}{1+{\frac {1}{a_{2k+1}}}}}{\underset {\text{assumption}}{\overset {\text{induction}}{\geq }}}1+{\frac {1}{1+{\frac {1}{a_{2k-1}}}}}=1+{\frac {1}{a_{2k}}}=a_{2k+1}$

Now, monotone decrease for even elements is shown, meaning $a_{2k+2}\leq a_{2k}$ for all $k\in \mathbb {N}$ .

Induction basis: $k=1$ .

$a_{4}=1+{\frac {1}{a_{3}}}=1+{\frac {1}{1+{\frac {1}{a_{2}}}}}=1+{\frac {1}{1+{\frac {3}{2}}}}=1+{\frac {1}{\frac {5}{2}}}=1+{\frac {2}{5}}={\frac {7}{5}}={\frac {14}{10}}\leq {\frac {15}{10}}={\frac {3}{2}}=a_{2}$

Induction step: $a_{2k+4}=1+{\frac {1}{a_{2k+3}}}=1+{\frac {1}{1+{\frac {1}{a_{2k+2}}}}}{\underset {\text{assumption}}{\overset {\text{induction}}{\leq }}}1+{\frac {1}{1+{\frac {1}{a_{2k}}}}}=1+{\frac {1}{a_{2k+1}}}=a_{2k+2}$

Part 3: By means of parts 1 and 2, we have that $(a_{2k})$ is monotonically decreasing, $(a_{2k-1})$ is monotonically increasing and both are bounded. The monotonicity criterion implies convergence of both subsequences.

Now, $\lim _{k\to \infty }a_{2k-1}=g=\lim _{k\to \infty }a_{2k}$ , since $\lim _{k\to \infty }a_{2k-1}={\tilde {a}}=\lim _{k\to \infty }a_{2k-3}$ , so there is

${\begin{aligned}&{\tilde {a}}=\lim _{k\to \infty }a_{2k-1}=\lim _{k\to \infty }\left(1+{\frac {1}{a_{2k-2}}}\right)=\lim _{k\to \infty }\left(1+{\frac {1}{1+{\frac {1}{a_{2k-3}}}}}\right)=\left(1+{\frac {1}{1+{\frac {1}{\tilde {a}}}}}\right)\\\iff &{\tilde {a}}=\left(1+{\frac {1}{\frac {{\tilde {a}}+1}{\tilde {a}}}}\right)=\left(1+{\frac {\tilde {a}}{{\tilde {a}}+1}}\right)={\frac {2{\tilde {a}}+1}{{\tilde {a}}+1}}\\\iff &{\tilde {a}}^{2}+{\tilde {a}}=2{\tilde {a}}+1\\\iff &{\tilde {a}}^{2}-{\tilde {a}}-1=0\end{aligned}}$

We resolve the quadratic equation, obtaining two solutions:

${\frac {1-{\sqrt {5}}}{2}}<0$

By means of part 1, there is $a_{n}>0$ , and hence $a_{2k-1}>0$ . So the latter solution must be the limit: $\lim _{k\to \infty }a_{2k-1}={\tilde {a}}={\tfrac {1+{\sqrt {5}}}{2}}=g\geq 0$ .

Analogously, $\lim _{k\to \infty }a_{2k}=g$ . Both subsequences converge to the same limit, so there must be

$\lim _{n\to \infty }a_{n}=g$

which finishes the proof.

Cauchy's limit theorem and the Cesàro mean

Exercise (Cauchy's limit theorem)

Prove Cauchy's limit theorem: Let $(a_{n})$ be a sequence converging to $a$ . Then, the Cesàro mean $\left({\frac {a_{1}+a_{2}+\ldots +a_{n}}{n}}\right)$ converges to $a$ .
Does the converse also hold true? I.e. if there is ${\frac {a_{1}+a_{2}+\ldots +a_{n}}{n}}\to a$ does this imply $a_{n}\to a$ ?
Use step 1 to show: $\lim \limits _{n\to \infty }{\frac {1+{\frac {1}{2}}+\ldots +{\frac {1}{n}}}{n}}=0$ .

Solution (Cauchy's limit theorem)

Since $(a_{n})$ converges to $a$ , for any $\epsilon >0$ there must be an $N\in \mathbb {N}$ such that for all $n\geq N$ there is:
$|a_{n}-a|<{\tfrac {\epsilon }{2}}$
But now, the sequence of means $\left({\frac {(a_{1}-a)+(a_{2}-a)+\ldots +(a_{N_{1}}-a)}{n}}\right)$ in $N_{1}$ will be dominated by terms ${\tfrac {\epsilon }{2}}$ if $N_{1}$ is much larger than $N$ . So for a large enough $N_{1}$ , the mean drops below $\epsilon$ . This can be done with even smaller $\epsilon$ , so for $N_{1}\geq N_{2}$ , there is even:
$\left|{\frac {(a_{1}-a)+(a_{2}-a)+\ldots +(a_{N_{1}}-a)}{n}}\right|<{\frac {\epsilon }{2}}$
For $n\geq \max\{N,N_{2}\}$ there is now
${\begin{aligned}\left|{\frac {a_{1}+a_{2}+\ldots +a_{n}}{n}}-a\right|&=\left|{\frac {a_{1}+a_{2}+\ldots +a_{n}}{n}}-{\frac {na}{a}}\right|\\[0.3em]&=\left|{\frac {a_{1}+a_{2}+\ldots +a_{n}-na}{n}}\right|\\[0.3em]&=\left|{\frac {a_{1}+a_{2}+\ldots +a_{n}-(\overbrace {a+a+\ldots +a} ^{n{\text{ times}}})}{n}}\right|\\[0.3em]&=\left|{\frac {(a_{1}-a)+(a_{2}-a)+\ldots +(a_{n}-a)}{n}}\right|\\[0.3em]&\leq \overbrace {\left|{\frac {(a_{1}-a)+(a_{2}-a)+\ldots +(a_{N}-a)}{n}}\right|} ^{<{\frac {\epsilon }{2}}}+\left|{\frac {(a_{N+1}-a)+(a_{N+2}-a)+\ldots +(a_{n}-a)}{n}}\right|\\[0.3em]&<{\frac {\epsilon }{2}}+{\frac {\overbrace {|a_{N+1}-a|} ^{<{\frac {\epsilon }{2}}}+\overbrace {|a_{N+2}-a|} ^{\frac {\epsilon }{2}}+\ldots +\overbrace {|a_{n}-a|} ^{<{\frac {\epsilon }{2}}}}{n}}\\[0.3em]&<{\frac {\epsilon }{2}}+{\frac {(n-N){\frac {\epsilon }{2}}}{n}}\\[0.3em]&<{\frac {\epsilon }{2}}+{\frac {n{\frac {\epsilon }{2}}}{n}}={\frac {\epsilon }{2}}+{\frac {\epsilon }{2}}=\epsilon \end{aligned}}$
and we have convergence.
No, the converse does not hold true. A counterexample is the sequence $(a_{n})=((-1)^{n})$ . It diverges (see the corresponding exercise above). However, for the Cesàro mean, there is ${\frac {a_{1}+a_{2}+\ldots +a_{n}}{n}}={\frac {-1+1-\ldots +(-1)^{n}}{n}}={\begin{cases}-{\frac {1}{n}}&\ {\text{ for odd }}n,\\{\frac {0}{n}}=0&\ {\text{ for even }}n\end{cases}}$ This is obviously a null sequence.
We apply Cauchy's limit theorem using $a_{n}={\frac {1}{n}}$ . Since $\lim _{n\to \infty }{\frac {1}{n}}=0$ there is also $\lim \limits _{n\to \infty }{\frac {1+{\frac {1}{2}}+\ldots +{\frac {1}{n}}}{n}}=0$ .