# Exercises: convergence and divergence – Serlo

Zur Navigation springen Zur Suche springen

## Proving convergence of a sequence

Exercise (Convergence of a sequence 1)

Use the epsilon-definition to prove that the sequence ${\displaystyle \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 ${\displaystyle n}$? The denominator stays constant at ${\displaystyle 2}$ , while the enumerator ${\displaystyle n^{2}}$ grows towards infinity. So the fraction ${\displaystyle {\frac {2}{n^{2}}}}$ should go to ${\displaystyle 0}$ .

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

${\displaystyle \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,

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

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

Solution (Convergence of a sequence 1)

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

{\displaystyle {\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 ${\displaystyle \left({\frac {{\sqrt {n}}-1}{{\sqrt {n}}+1}}\right)_{n\in \mathbb {N} }}$ converges to ${\displaystyle 1}$ .

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

For the epsilon-definition, we need to verify:

${\displaystyle \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 ${\displaystyle \epsilon }$, we need to find a suitable ${\displaystyle N}$, such that for ${\displaystyle \left|{\frac {{\sqrt {n}}-1}{{\sqrt {n}}+1}}-1\right|<\epsilon }$ holds after the sequence has passed element number ${\displaystyle N}$. So let us find such an ${\displaystyle N}$ by re-shaping the condition:

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

{\displaystyle {\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 ${\displaystyle ((-1)^{n})_{n\in \mathbb {N} }}$ diverges.

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

We need to show that

${\displaystyle \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 ${\displaystyle 1}$ and ${\displaystyle -1}$, the only possible limits are ${\displaystyle a=-1}$ and ${\displaystyle a=1}$. However, we have to show the above statement for all ${\displaystyle a\in \mathbb {R} }$ in order to prove divergence.

First, let us consider the case ${\displaystyle a<0}$: For all even ${\displaystyle n\in \mathbb {N} }$ there is ${\displaystyle (-1)^{n}-a=1-a\geq 1}$, so

${\displaystyle |(-1)^{n}-a|=|1-a|\geq 1}$

That means, we are further away from ${\displaystyle a}$ than ${\displaystyle \epsilon =1}$ . For any ${\displaystyle N\in \mathbb {N} }$ there will be an even ${\displaystyle n\in \mathbb {N} }$ with ${\displaystyle n\geq N}$, such that

${\displaystyle |(-1)^{n}-a|\geq 1\geq \epsilon }$

Analogously, for ${\displaystyle a\geq 0}$ and all odd ${\displaystyle n\in \mathbb {N} }$:

${\displaystyle |(-1)^{n}-a|=|-1-a|\geq 1}$, since ${\displaystyle -1-a\leq -1}$

So if we choose again ${\displaystyle \epsilon =1}$ , then for each ${\displaystyle N\in \mathbb {N} }$ there will be an odd ${\displaystyle n\in \mathbb {N} }$ with ${\displaystyle n\geq N}$, such that

${\displaystyle |(-1)^{n}-a|\geq 1\geq \epsilon }$

I.e. for all ${\displaystyle a\in \mathbb {R} }$, the sequence has infinitely many elements staying away by more than 1 from ${\displaystyle a}$ and hence, the sequence diverges.

Proof (Divergence of an alternating sequence)

Case 1: Let ${\displaystyle a<0}$. Choose ${\displaystyle \epsilon =1}$ and ${\displaystyle N\in \mathbb {N} }$ arbitrary. Now, take an even ${\displaystyle n}$ with ${\displaystyle n\geq N}$. Then,

${\displaystyle |(-1)^{n}-a|=|1-a|\geq 1}$

Case 2: Let ${\displaystyle a\geq 0}$. Choose ${\displaystyle \epsilon =1}$ and ${\displaystyle N\in \mathbb {N} }$ arbitrary. Now, take an odd ${\displaystyle n}$ with ${\displaystyle n\geq N}$. Then,

${\displaystyle |(-1)^{n}-a|=|-1-a|\geq 1}$

For two subsequence elements ${\displaystyle a_{n}}$ and ${\displaystyle a_{n+1}}$ there is always ${\displaystyle |a_{n}-a_{n+1}|=|(-1)^{n}-(-1)^{n+1}|=|\pm 2|=2.}$. So if for ${\displaystyle \epsilon =1>0}$ there was an ${\displaystyle N\in \mathbb {N} }$ and an ${\displaystyle a\in \mathbb {R} }$ with

${\displaystyle |(-1)^{n}-a|<\epsilon \ \forall n\geq N}$

then, we would have

${\displaystyle 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 ${\displaystyle k\in \mathbb {N} }$ and a given sequence ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ converging as ${\displaystyle \lim _{n\to \infty }a_{n}=a}$ the ${\displaystyle k}$-th power of this sequence will also converge to ${\displaystyle \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

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

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

${\displaystyle 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:

${\displaystyle {\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 ${\displaystyle x=a_{n}}$ and ${\displaystyle y=a}$:

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

${\displaystyle |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 ${\displaystyle \sum \limits _{j=0}^{k-1}|a_{n}|^{k-1-j}|a|^{j}}$ is bounded from above by a constant, then ${\displaystyle |a_{n}^{k}-a^{k}|}$ gets arbitrarily small and we are done. Now, we know that ${\displaystyle (a_{n})}$ converges, so it is bounded. We call this bound ${\displaystyle M>0}$ with ${\displaystyle |a_{n}|\leq M}$ for all ${\displaystyle n\in \mathbb {N} }$. Therefore, ${\displaystyle \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, ${\displaystyle |a_{n}^{k}-a^{k}|}$ gets arbitrarily small (below any ${\displaystyle \epsilon >0}$) and we have convergence ${\displaystyle \lim _{n\to \infty }a_{n}^{k}=a^{k}}$.

Proof (Powers of sequences)

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

{\displaystyle {\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 ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$, ${\displaystyle (b_{n})_{n\in \mathbb {N} }}$, ${\displaystyle (c_{n})_{n\in \mathbb {N} }}$, ${\displaystyle (d_{n})_{n\in \mathbb {N} }}$, ${\displaystyle (e_{n})_{n\in \mathbb {N} }}$ and ${\displaystyle (f_{n})_{n\in \mathbb {N} }}$ converge. Determine the limit in the respective case.

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

Solution (Limits of sequences)

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

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

${\displaystyle 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 ${\displaystyle n^{2}}$-terms cancel and we get a finite limit:

${\displaystyle 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 ${\displaystyle n}$? At first glance, we go to ${\displaystyle \infty -\infty }$ which is no determinate result. but after some simplifications:

${\displaystyle 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)

${\displaystyle \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 ${\displaystyle \lim _{n\to \infty }b_{n}=0=\lim _{n\to \infty }c_{n}}$. The squeeze theorem hence yields ${\displaystyle \lim _{n\to \infty }d_{n}=0}$.

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

${\displaystyle 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 ${\displaystyle 1+2+\ldots +n={\tfrac {n(n+1)}{2}}}$. Then, we get two polynomials of degree 2, where we can factor out an ${\displaystyle n^{2}}$:

${\displaystyle 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: "${\displaystyle 1+2+\ldots +n}$ is a polynomial of degree 1" and to factor out an ${\displaystyle n}$. This will not yield the desired result, as the number of summands in this polynomial depends in ${\displaystyle n}$. If you have a sum whose number of elements increases in ${\displaystyle 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 ${\displaystyle \infty }$-many summands, so the limit is not necessarily 0.

Exercise (Sequences depending on a parameter)

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

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

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

Proof (Sequences depending on a parameter)

Case 1: For ${\displaystyle |z|\leq 1}$ there is

${\displaystyle \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 ${\displaystyle \lim _{n\to \infty }{\frac {z^{n}}{n}}=0}$.

Case 2: For ${\displaystyle |z|>1}$ there is

${\displaystyle \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 ${\displaystyle \lim _{n\to \infty }{\frac {n}{z^{n}}}=0}$.

## Exponential sequences

Exercise (Exponential sequences)

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

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

Solution (Exponential sequences)

1.We make use of ${\displaystyle \left(1+{\frac {1}{n}}\right)^{n}\to e}$:

${\displaystyle \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 ${\displaystyle \left(1+{\frac {1}{n}}\right)^{n}\to e}$:

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

{\displaystyle {\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 ${\displaystyle \left(1+{\frac {1}{n}}\right)^{n}\to e}$, we will extend both the enumerator and the denominator by ${\displaystyle \left(1+{\frac {1}{n}}\right)}$

${\displaystyle 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 ${\displaystyle \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 ${\displaystyle \lim _{n\to \infty }\left(1-{\tfrac {1}{n^{2}}}\right)^{n}=1}$, then we directly get

${\displaystyle 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 ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$:

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

Solution (Squeeze theorem)

1. For ${\displaystyle k\in \mathbb {N} }$ we have the upper and lower bound

${\displaystyle \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 ${\displaystyle \lim _{n\to \infty }b_{n}=0=\lim _{n\to \infty }c_{n}}$. The squeeze theorem now implies ${\displaystyle \lim _{n\to \infty }a_{n}=\lim _{n\to \infty }{\tfrac {(-1)^{n}}{n^{k}}}=0}$.

2. For ${\displaystyle n\geq 4}$ there is ${\displaystyle 2^{n}\geq n^{2}}$, which gives an upper bound. For the lower bound, we just use 0:

${\displaystyle \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 ${\displaystyle \lim _{n\to \infty }b_{n}=0=\lim _{n\to \infty }c_{n}}$ the squeeze theorem renders ${\displaystyle \lim _{n\to \infty }a_{n}=\lim _{n\to \infty }{\tfrac {n^{n}}{2^{n^{2}}}}=0}$.

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

${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \lim _{n\to \infty }a_{n}=1}$.

4. For ${\displaystyle x\geq y}$, there is

${\displaystyle \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 ${\displaystyle \lim _{n\to \infty }b_{n}=\lim _{n\to \infty }{\sqrt[{n}]{\alpha }}\cdot x=1\cdot x}$ and ${\displaystyle \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 ${\displaystyle \lim _{n\to \infty }a_{n}=x}$.

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

Both cases can be concluded as ${\displaystyle \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

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

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

{\displaystyle {\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 ${\displaystyle \lim _{n\to \infty }a_{n}={\tfrac {1}{4}}}$.

6. There is

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

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

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

Exercise (Squeeze theorem for products of roots)

Prove that ${\displaystyle \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 ${\displaystyle |{\sqrt {n}}({\sqrt[{n}]{n}}-1)|={\sqrt {n}}({\sqrt[{n}]{n}}-1)}$ which converges to 0. That means, we have to show that ${\displaystyle ({\sqrt[{n}]{n}}-1)}$ goes to 0 fast enough. More explicitly, we need that ${\displaystyle ({\sqrt[{n}]{n}}-1)^{n}}$ decreases as a sufficiently large power of ${\displaystyle n}$. We consider ${\displaystyle n\geq 4}$:

{\displaystyle {\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

{\displaystyle {\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 ${\displaystyle ({\sqrt[{n}]{n}}-1)}$ by a sufficient power of ${\displaystyle n}$

${\displaystyle |{\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 ${\displaystyle \lim _{n\to \infty }{\sqrt {n}}({\sqrt[{n}]{n}}-1)=0}$.

## Monotony criterion and recursively defined sequences

Exercise (Monotony criterion)

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

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

converges.

Solution (Monotony criterion)

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

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

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

${\displaystyle {\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: ${\displaystyle (a_{n})}$ is bounded from below by ${\displaystyle 0}$ , i.e ${\displaystyle a_{n}\geq 0}$ ${\displaystyle \forall n\in \mathbb {N} }$.

This can be shown by induction in ${\displaystyle n}$:

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

Induction step: ${\displaystyle 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: ${\displaystyle (a_{n})}$ actually converges.

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

Exercise (Convergence of a recursively defined sequence 1)

Why does the recursively defined sequence

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

converge? Determine its limit:

1. By finding an explicit form of the sequence
2. Using the monotony criterion

Solution (Convergence of a recursively defined sequence 1)

Part 1: Let us investigate the first sequence elements

{\displaystyle {\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:

{\displaystyle {\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 ${\displaystyle a_{n}={\frac {3^{n}-2^{n}}{3^{n}}}}$ for all ${\displaystyle n\in \mathbb {N} _{0}}$ . Let us prove the assertion by induction over ${\displaystyle n}$:

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

Induction step: ${\displaystyle 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 ${\displaystyle a_{n}={\tfrac {3^{n}-2^{n}}{3^{n}}}}$ for all ${\displaystyle 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:

${\displaystyle \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: ${\displaystyle (a_{n})}$ is monotonously increasing, i.e. ${\displaystyle a_{n+1}\geq a_{n}}$ ${\displaystyle \forall n\in \mathbb {N} _{0}}$.

The proof runs by induction over ${\displaystyle n}$:

Induction basis: ${\displaystyle n=1}$. ${\displaystyle 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: ${\displaystyle 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: ${\displaystyle (a_{n})}$ is bounded from above by ${\displaystyle 1}$ , i.e. ${\displaystyle a_{n}\leq 1}$ ${\displaystyle \forall n\in \mathbb {N} _{0}}$.

This can also be shown inductively:

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

Induction step: ${\displaystyle 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: ${\displaystyle (a_{n})}$ converges.

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

Step 4: computing the limit.

An index shift will not affect the limit: ${\displaystyle \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:

${\displaystyle \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 ${\displaystyle a}$:

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

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

Exercise (convergence of a recursively defined sequence 2)

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

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

{\displaystyle {\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 ${\displaystyle n}$ times and get

{\displaystyle {\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 ${\displaystyle a_{n}-a_{n-1}}$ are multiples of ${\displaystyle (b-a)}$ We obtain ${\displaystyle a_{n}}$ by adding up all differences (telescoping sum)

${\displaystyle \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:

${\displaystyle 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 ${\displaystyle \lim _{n\to \infty }(-{\tfrac {3}{5}})^{n}=0}$ so the limit theorems yield

${\displaystyle \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 (Monotony criterion for sequences)

Show the the sequence ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ defined by the recursion relation

${\displaystyle a_{1}=1,\ a_{n+1}={\sqrt {1+a_{n}}}}$

converges to the so-called golden ratio ${\displaystyle g={\tfrac {1+{\sqrt {5}}}{2}}}$ .

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

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

Why is it monotonous? Let us compute the first sequence elements:

${\displaystyle 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 ${\displaystyle (a_{n})}$ is monotonously increasing. Only a proof is required, e.g. by induction. Then, we need an upper bound. The limit of ${\displaystyle (a_{n})}$ shall be ${\displaystyle g={\tfrac {1+{\sqrt {5}}}{2}}}$ , so any number greater than ${\displaystyle g}$ will be an upper bound. Since ${\displaystyle g={\tfrac {1+{\sqrt {5}}}{2}}\leq {\tfrac {1+{\sqrt {9}}}{2}}={\tfrac {1+3}{2}}={\tfrac {4}{2}}=2}$ w simply choose ${\displaystyle 2}$ as an upper bound for ${\displaystyle (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 ${\displaystyle g}$ is the limit and we are done.

Solution (Monotony criterion for sequences)

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

The proof is by induction over ${\displaystyle n}$:

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

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

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

The proof is again done by induction:

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

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

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

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

${\displaystyle (a_{n})}$ is monotonously increasing and bounded, so it converges by the monotony criterion.

Step 4: computing the limit.

An index shift will not change the limit: ${\displaystyle \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

${\displaystyle \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 ${\displaystyle a={\sqrt {1+a}}}$ for ${\displaystyle a}$ and obtain

${\displaystyle a={\sqrt {1+a}}\Rightarrow a^{2}=1+a\Rightarrow a^{2}-a-1=0}$

Which has two solutions:

${\displaystyle x_{1,2}={\frac {1\pm {\sqrt {1+4}}}{2}}={\frac {1\pm {\sqrt {5}}}{2}}}$

I.e. ${\displaystyle a_{1}={\tfrac {1+{\sqrt {5}}}{2}}}$ and ${\displaystyle x_{2}={\tfrac {1-{\sqrt {5}}}{2}}}$. Which one is the limit? There is ${\displaystyle x_{2}={\tfrac {1-{\sqrt {5}}}{2}}<0}$. Since ${\displaystyle a_{1}=1}$ and monotony, the limit of ${\displaystyle (a_{n})}$ can only be above ${\displaystyle 1}$ . Hence, ${\displaystyle x_{2}}$ can not be the limit and we have convergence to ${\displaystyle x_{1}}$ .

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

Exercise (Monotony criterion for sequences)

Show that the sequence ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$, defined by

${\displaystyle a_{1}=1,\ a_{n+1}=1+{\frac {1}{a_{n}}}}$

converges to the golden ratio ${\displaystyle g={\tfrac {1+{\sqrt {5}}}{2}}}$ . Do this by showing

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

Solution (Monotony criterion for sequences)

Part 1: is done by induction over ${\displaystyle n}$:

Induction basis: ${\displaystyle n=1}$.

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

Induction step:

${\displaystyle 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 ${\displaystyle n}$:

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

Induction basis: ${\displaystyle k=1}$.

${\displaystyle 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:

${\displaystyle 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, monotonous decrease for even elements is shown, meaning ${\displaystyle a_{2k+2}\leq a_{2k}}$ for all ${\displaystyle k\in \mathbb {N} }$.

Induction basis: ${\displaystyle k=1}$.

${\displaystyle 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:

${\displaystyle 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 ${\displaystyle (a_{2k})}$ is monotonously decreasing, ${\displaystyle (a_{2k-1})}$ is monotonously increasing and both are bounded. The monotony criterion implies convergence of both subsequences.

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

{\displaystyle {\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:

${\displaystyle {\frac {1-{\sqrt {5}}}{2}}<0}$ and ${\displaystyle {\frac {1+{\sqrt {5}}}{2}}>0}$

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

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

${\displaystyle \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)

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

Solution (Cauchy's limit theorem)

1. Since ${\displaystyle (a_{n})}$ converges to ${\displaystyle a}$ , for any ${\displaystyle \epsilon >0}$ there must be an ${\displaystyle N\in \mathbb {N} }$ such that for all ${\displaystyle n\geq N}$ there is:
${\displaystyle |a_{n}-a|<{\tfrac {\epsilon }{2}}}$

But now, the sequence of means ${\displaystyle \left({\frac {(a_{1}-a)+(a_{2}-a)+\ldots +(a_{N_{1}}-a)}{n}}\right)}$ in ${\displaystyle N_{1}}$ will be dominated by terms ${\displaystyle {\tfrac {\epsilon }{2}}}$ if ${\displaystyle N_{1}}$ is much larger than ${\displaystyle N}$. So for a large enough ${\displaystyle N_{1}}$, the mean drops below ${\displaystyle \epsilon }$. This can be done with even smaller ${\displaystyle \epsilon }$, so for ${\displaystyle N_{1}\geq N_{2}}$, there is even:

${\displaystyle \left|{\frac {(a_{1}-a)+(a_{2}-a)+\ldots +(a_{N_{1}}-a)}{n}}\right|<{\frac {\epsilon }{2}}}$

For ${\displaystyle n\geq \max\{N,N_{2}\}}$ there is now

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

2. No, the converse does not hold true. A counterexample is the sequence ${\displaystyle (a_{n})=((-1)^{n})}$. It diverges (see the corresponding exercise above). However, for the Cesàro mean, there is
${\displaystyle {\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.

3. We apply Cauchy's limit theorem using ${\displaystyle a_{n}={\frac {1}{n}}}$. Since ${\displaystyle \lim _{n\to \infty }{\frac {1}{n}}=0}$ there is also ${\displaystyle \lim \limits _{n\to \infty }{\frac {1+{\frac {1}{2}}+\ldots +{\frac {1}{n}}}{n}}=0}$.