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

verweis=Math for Non-Geeks

Proving convergence of a sequence

Exercise (Convergence of a sequence 1)

Use the epsilon-definition to prove that the sequence ${(\frac{2}{n^{2}})}_{n \in ℕ}$ 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 ϵ > 0 \exists N \in ℕ \forall n \geq N : | \frac{2}{n^{2}} - 0 | = \frac{2}{n^{2}} < ϵ$

Now,

$\begin{matrix} \frac{2}{n^{2}} < ϵ \\ ⟺ & 2 < n^{2} ϵ \\ ⟺ & \frac{2}{ϵ} < n^{2} \\ ⟺ & n > \sqrt{\frac{2}{ϵ}} \end{matrix}$

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

Solution (Convergence of a sequence 1)

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

$\begin{matrix} | \frac{2}{n^{2}} - 0 | & = \frac{2}{n^{2}} \\ \leq \frac{2}{N^{2}} \\ < ϵ . \end{matrix}$

Exercise (Convergence of a sequence 2)

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

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

For the epsilon-definition, we need to verify: $\forall ϵ > 0 \exists N \in ℕ \forall n \geq N : | \frac{\sqrt{n} - 1}{\sqrt{n} + 1} - 1 | < ϵ$ This means, for each $ϵ$ , we need to find a suitable $N$ , such that for $| \frac{\sqrt{n} - 1}{\sqrt{n} + 1} - 1 | < ϵ$ holds after the sequence has passed element number $N$ . So let us find such an $N$ by re-shaping the condition:

$\begin{matrix} | \frac{\sqrt{n} - 1}{\sqrt{n} + 1} - 1 | < ϵ & \Leftrightarrow | \frac{\sqrt{n} - 1 - \sqrt{n} - 1}{\sqrt{n} + 1} | < ϵ \\ \Leftrightarrow | \frac{- 2}{\sqrt{n} + 1} | < ϵ \\ \Leftrightarrow \frac{2}{\sqrt{n} + 1} < ϵ \\ \Leftrightarrow \sqrt{n} + 1 > \frac{2}{ϵ} \\ \Leftrightarrow \sqrt{n} > \frac{2}{ϵ} - 1 \\ \Leftrightarrow n > {(\frac{2}{ϵ} - 1)}^{2} \end{matrix}$

That means, we need an $N \in ℕ$ with $N > {(\frac{2}{ϵ} - 1)}^{2}$ . This exists by the Archimedean axiom, and we are done with the proof.

Solution (Convergence of a sequence 2)

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

$\begin{matrix} | \frac{\sqrt{n} - 1}{\sqrt{n} + 1} - 1 | & = | \frac{- 2}{\sqrt{n} + 1} | \\ = \frac{2}{\sqrt{n} + 1} \\ \leq \frac{2}{\sqrt{N} + 1} \\ < ϵ . \end{matrix}$

Proving divergence for an alternating sequence

Exercise (Divergence of an alternating sequence)

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

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

We need to show that $\forall a \in ℝ \exists ϵ > 0 \forall N \in ℕ \exists n \geq N : | (- 1)^{n} - a | \geq ϵ$ 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 ℝ$ in order to prove divergence.

First, let us consider the case $a < 0$ : For all even $n \in ℕ$ 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 $ϵ = 1$ . For any $N \in ℕ$ there will be an even $n \in ℕ$ with $n \geq N$ , such that $| (- 1)^{n} - a | \geq 1 \geq ϵ$

Analogously, for $a \geq 0$ and all odd $n \in ℕ$ : $| (- 1)^{n} - a | = | - 1 - a | \geq 1$ So if we choose again $ϵ = 1$ , then for each $N \in ℕ$ there will be an odd $n \in ℕ$ with $n \geq N$ , such that $| (- 1)^{n} - a | \geq 1 \geq ϵ$ I.e. for all $a \in ℝ$ , 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 $ϵ = 1$ and $N \in ℕ$ 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 $ϵ = 1$ and $N \in ℕ$ 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 $ϵ = 1 > 0$ there was an $N \in ℕ$ and an $a \in ℝ$ with $| (- 1)^{n} - a | < ϵ \forall n \geq N$ then, we would have $\begin{matrix} 2 & = | (- 1)^{N} - (- 1)^{N + 1} | = | (- 1)^{N} - a + a - (- 1)^{N + 1} | \\ \underset{inequality}{\overset{triangle-}{\leq}} | (- 1)^{N} - a | + | a - (- 1)^{N + 1} | = | (- 1)^{N} - a | + | (- 1)^{N} - a | < ϵ + ϵ = 1 + 1 = 2 ↯ \end{matrix}$

Powers of sequences

Exercise (Powers of sequences)

For any power $k \in ℕ$ and a given sequence $(a_{n})_{n \in ℕ}$ 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 $ϵ > 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} + \dots + 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{matrix} \sum_{j = 0}^{k - 1} x^{k - 1 - j} y^{j} & = x^{k - 1} y^{0} + x^{k - 2} y^{1} + \dots + x^{1} y^{k - 2} + x^{0} y^{k - 1} \\ ↓ multiply both sides with y \\ \Rightarrow & y \sum_{j = 0}^{k - 1} x^{k - 1 - j} y^{j} & = x^{k - 1} y^{1} + x^{k - 2} y^{2} + \dots + x^{1} y^{k - 1} + x^{0} y^{k} \\ ↓ multiply with x and subtract both expressions \\ \Rightarrow & x \sum_{j = 0}^{k - 1} x^{k - 1 - j} y^{j} - y \sum_{j = 0}^{k - 1} x^{k - 1 - j} y^{j} & = (x^{k} y^{0} + x^{k - 1} y^{1} + \dots + x^{2} y^{k - 2} + x^{1} y^{k - 1}) \\ - (x^{k - 1} y^{1} + x^{k - 2} y^{2} \dots + x^{1} y^{k - 1} + x^{0} y^{k}) \\ = x^{k} - y^{k} \\ ↓ factor out \sum_{j = 0}^{k - 1} x^{k - 1 - j} y^{j} \\ \Rightarrow & (x - y) \cdot \sum_{j = 0}^{k - 1} x^{k - 1 - j} y^{j} & = x^{k} - y^{k} \\ ↓ \cdot \frac{1}{x - y} \\ \Rightarrow & \sum_{j = 0}^{k - 1} x^{k - 1 - j} y^{j} & = \frac{x^{k} - y^{k}}{x - y} \end{matrix}$

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

$| a_{n}^{k} - a^{k} | = | (a_{n} - a) \sum_{j = 0}^{k - 1} a_{n}^{k - 1 - j} a^{j} | = | (a_{n} - a) | \cdot | \sum_{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_{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_{j = 0}^{k - 1} | a_{n} |^{k - 1 - j} | a |^{j}$

If we can now show that the second factor $\sum_{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 ℕ$ . Therefore, $\sum_{j = 0}^{k - 1} | a_{n} |^{k - 1 - j} | a |^{j} \leq \sum_{j = 0}^{k - 1} M^{k - 1 - j} | a |^{j} = C < \infty$ .

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

Proof (Powers of sequences)

Let $ϵ > 0$ be arbitrary. Since $(a_{n})$ converges, there must be an $M > 0$ with $| a_{n} | \leq M$ for all $n \in ℕ$ . Since $lim_{n \to \infty} a_{n} = a$ there is an $N \in ℕ$ with $| a_{n} - a | < \frac{ϵ}{C}$ for all $n \geq N$ , where we define the constant $C = \sum_{j = 0}^{k - 1} M^{k - 1 - j} | a |^{j}$ . Let now $n \geq N$ be arbitrary. Then

$\begin{matrix} | a_{n}^{k} - a^{k} | & \underset{formula}{\overset{auxiliary}{=}} | a_{n} - a | \cdot | \sum_{j = 0}^{k - 1} a_{n}^{k - 1 - j} a^{j} | \\ ↓ triangle inequality \\ \leq | a_{n} - a | \cdot \sum_{j = 0}^{k - 1} | a_{n} |^{k - 1 - j} | a |^{j} \\ ↓ (a_{n}) bounded \\ \leq | a_{n} - a | \cdot \underset{= C}{\underset{⏟}{\sum_{j = 0}^{k - 1} M^{k - 1 - j} | a |^{j}}} \\ < \frac{ϵ}{C} \cdot C \\ = ϵ \end{matrix}$

Limit theorems

Exercise (Limits of sequences)

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

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

Solution (Limits of sequences)

1. The trick is to split the roots $\sqrt[n]{n^{3}}$ and $\sqrt[n]{3 n}$ 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]{3 n}} = \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{theorems}{\overset{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 the 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{2 n^{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{theorems}{\overset{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}}{3 n} = \frac{n^{2} + 4 n + 4 - n^{2}}{3 n} = \frac{4 n + 4}{3 n} = \frac{4 + \frac{4}{n}}{3} \underset{theorems}{\overset{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{theorems}{\overset{limit-}{\to}} \frac{0}{\sqrt{1 + 0} + 1} = 0$

Alternative solution: (squeeze theorem)

$\underset{= b_{n}}{\underset{⏟}{0}} \leq \underset{= d_{n}}{\underset{⏟}{\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}} \leq \underset{= c_{n}}{\underset{⏟}{\frac{1}{\sqrt{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}{3 n + 2} = \frac{\sqrt{1 + \frac{1}{n^{2}}} + 1}{3 + \frac{2}{n}} \underset{theorems}{\overset{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 + \dots + n = \frac{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 + \dots + n}{n^{2}} \underset{sum formula}{\overset{arithmetic}{=}} \frac{\frac{n (n + 1)}{2}}{n^{2}} = \frac{n^{2} + n}{2 n^{2}} = \frac{1 + \frac{1}{n}}{2} \underset{theorems}{\overset{limit-}{\to}} \frac{1 + 0}{2} = \frac{1}{2}$

Warning

It is tempting to think: " $1 + 2 + \dots + 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 on $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 ℕ}$ with $a_{n} = \frac{n + z^{n}}{n - z^{n}}$ converges, depending on the parameter $z \in ℝ$ .

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{theorems}{\overset{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{theorems}{\overset{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 ℕ}$ , $(b_{n})_{n \in ℕ}$ , $(c_{n})_{n \in ℕ}$ and $(d_{n})_{n \in ℕ}$ for converges. If they converge, determine the limit.

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

Solution (Exponential sequences)

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

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

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

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

$d_{n} = {(1 - \frac{1}{n})}^{n} = {(\frac{n - 1}{n})}^{n} \overset{n \geq 2}{=} \frac{1}{{(\frac{n}{n - 1})}^{n}} = \frac{1}{{(\frac{n - 1 + 1}{n - 1})}^{n}} = \frac{1}{{(1 + \frac{1}{n - 1})}^{n}} \underset{theorems}{\overset{limit-}{\to}} \frac{1}{e}$ since $lim_{n \to \infty} {(1 + \frac{1}{n})}^{n + 1} = lim_{n \to \infty} {(1 + \frac{1}{n - 1})}^{n} = e$

Alternative solution: If we already know that $lim_{n \to \infty} {(1 - \frac{1}{n^{2}})}^{n} = 1$ , then we directly get

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

Squeeze theorem

Exercise (Squeeze theorem)

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

$a_{n} = \frac{(- 1)^{n}}{n^{k}}$ for $k \in ℕ$
$a_{n} = \frac{n^{n}}{2^{n^{2}}}$
$a_{n} = \sqrt[n]{n^{s}}$ for $s \in ℚ^{+}$
$a_{n} = \sqrt[n]{α x^{n} + β y^{n}}$ for $α, β, x, y \geq 0$
$a_{n} = \frac{1}{n} \sum_{k = 1}^{n} \frac{k^{3} + n^{2}}{n^{3} + k^{2}}$
$a_{n} = {(1 - \frac{1}{n^{4}})}^{n}$

Solution (Squeeze theorem)

1. For $k \in ℕ$ we have the upper and lower bound $\underset{= b_{n}}{\underset{⏟}{- \frac{1}{n}}} \leq \underset{= a_{n}}{\underset{⏟}{\frac{(- 1)^{n}}{n^{k}}}} \leq \underset{= c_{n}}{\underset{⏟}{\frac{1}{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} \frac{(- 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: $\underset{= b_{n}}{\underset{⏟}{0}} \leq \underset{= a_{n}}{\underset{⏟}{\frac{n^{n}}{2^{n^{2}}}}} = \frac{n^{n}}{2^{n \cdot n}} = \frac{n^{n}}{(2^{n})^{n}} = {(\frac{n}{2^{n}})}^{n} \leq {(\frac{n}{n^{2}})}^{n} = {(\frac{1}{n})}^{n} = \frac{1}{n^{n}} \leq \underset{= c_{n}}{\underset{⏟}{\frac{1}{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} \frac{n^{n}}{2^{n^{2}}} = 0$ .

3. For $s \in ℚ^{+}$ we can find some $k \in ℕ$ 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:

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

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

$\underset{= b_{n}}{\underset{⏟}{\sqrt[n]{α} \cdot x}} = \sqrt[n]{α x^{n}} \leq \underset{= a_{n}}{\underset{⏟}{\sqrt[n]{α x^{n} + y^{n}}}} \leq \sqrt[n]{α x^{n} + β x^{n}} = \sqrt[n]{(α + β) x^{n}} = \sqrt[n]{α + β} \cdot \sqrt[n]{x^{n}} = \underset{= c_{n}}{\underset{⏟}{\sqrt[n]{α + β} \cdot x}}$

The limits of the bounding sequences are $lim_{n \to \infty} b_{n} = lim_{n \to \infty} \sqrt[n]{α} \cdot x = 1 \cdot x$ and $lim_{n \to \infty} c_{n} = lim_{n \to \infty} \sqrt[n]{α + β} \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

$\underset{= b_{n}}{\underset{⏟}{\frac{1}{n} \sum_{k = 1}^{n} \frac{k^{3}}{n^{3} + n^{2}}}} \leq \underset{= a_{n}}{\underset{⏟}{\frac{1}{n} \sum_{k = 1}^{n} \frac{k^{3} + n^{2}}{n^{3} + k^{2}}}} \leq \underset{= c_{n}}{\underset{⏟}{\frac{1}{n} \sum_{k = 1}^{n} \frac{k^{3} + n^{2}}{n^{3}}}}$

Those bounding sequences converge to

$\begin{matrix} 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{formula}{\overset{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} + 2 n^{3} + n^{2}}{4 n^{4} + 4 n^{3}} = lim_{n \to \infty} \frac{1 + \frac{2}{n} + \frac{1}{n^{2}}}{4 + \frac{4}{n}} = \frac{1}{4} \end{matrix}$

and

$\begin{matrix} 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}} (\sum_{k = 1}^{n} k^{3} + \sum_{k = 1}^{n} n^{2}) \underset{formula}{\overset{sum-}{=}} lim_{n \to \infty} \frac{1}{n^{4}} \cdot (\frac{n^{2} (n + 1)^{2}}{4} + n \cdot n^{2}) \\ = lim_{n \to \infty} (\frac{n^{4} + 2 n^{3} + 2 n^{2}}{4 n^{4}} + \frac{n^{3}}{n^{4}}) = 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{matrix}$

So by means of the squeeze theorem $lim_{n \to \infty} a_{n} = \frac{1}{4}$ .

6. There is

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

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{matrix} n & = (\sqrt[n]{n})^{n} \\ = ((\sqrt[n]{n} - 1) + 1)^{n} \\ ↓ binomial theorem \\ = \sum_{k = 0}^{n} (\binom{n}{k}) (\sqrt[n]{n} - 1)^{k} \cdot \underset{= 1}{\underset{⏟}{1^{n - k}}} \\ = \underset{= 1}{\underset{⏟}{(\binom{n}{0}) (\sqrt[n]{n} - 1)^{0}}} + \underset{\geq 0}{\underset{⏟}{\sum_{k = 1}^{2} (\binom{n}{k}) (\sqrt[n]{n} - 1)^{k}}} + (\binom{n}{3}) (\sqrt[n]{n} - 1)^{3} + \underset{\geq 0}{\underset{⏟}{\sum_{k = 4}^{n} (\binom{n}{k}) (\sqrt[n]{n} - 1)^{k}}} \\ \geq 1 + (\binom{n}{3}) (\sqrt[n]{n} - 1)^{3} \\ = 1 + \frac{n (n - 1) (n - 2)}{6} (\sqrt[n]{n} - 1)^{3} \end{matrix}$

This implies

$\begin{matrix} 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} \\ \Leftrightarrow \frac{6}{n (n - 2)} \geq (\sqrt[n]{n} - 1)^{3} \\ \Leftrightarrow \sqrt[n]{n} - 1 \leq \sqrt[3]{\frac{6}{n (n - 2)}} \underset{n - 2 \geq \frac{n}{2}}{\overset{n \geq \frac{n}{2}}{\leq}} \sqrt[3]{\frac{6}{(\frac{n}{2})^{2}}} = \sqrt[3]{\frac{24}{n^{2}}} \end{matrix}$

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]{\frac{24}{n^{2}}} = \sqrt[3]{24} \cdot \frac{n^{\frac{1}{2}}}{n^{\frac{2}{3}}} = \sqrt[3]{24} \cdot \frac{1}{n^{\frac{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 ℕ}$ be a sequence with $0 < b_{n} < 1$ for all $n \in ℕ$ . Show, using the monotonicity criterion that in this case the product sequence $(a_{n})_{n \in ℕ}$ defined as

$a_{n} = \prod_{k = 1}^{n} b_{k} = b_{1} \cdot b_{2} \cdot \dots \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} ⟺ \frac{a_{n + 1}}{a_{n}} \leq 1$ $\forall n \in ℕ$ .

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

$\frac{a_{n + 1}}{a_{n}} = \frac{\prod_{k = 1}^{n + 1} b_{k}}{\prod_{k = 1}^{n} b_{k}} = \frac{(\prod_{k = 1}^{n} b_{k}) \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 ℕ$ .

This can be shown by induction in $n$ :

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

Induction step: $a_{n + 1} = \prod_{k = 1}^{n + 1} b_{k} = \underset{\overset{assumption}{\geq} 0}{\underset{⏟}{(\prod_{k = 1}^{n} b_{k})}} \cdot \underset{\geq 0}{\underset{⏟}{b_{n + 1}}} \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{matrix} a_{0} & = 0 \\ a_{1} & = \frac{2}{3} a_{0} + \frac{1}{3} = \frac{2}{3} \cdot 0 + \frac{1}{3} = \frac{1}{3} \\ 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} \\ 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} \\ 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} \\ ⋮ \end{matrix}$

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

$\begin{matrix} a_{0} & = 0 \\ a_{1} & = \frac{1}{3} = \frac{3 - 2}{3} = \frac{3^{1} - 2^{1}}{3^{1}} \\ a_{2} & = \frac{5}{9} = \frac{9 - 4}{9} = \frac{3^{2} - 2^{2}}{3^{2}} \\ a_{3} & = \frac{19}{27} = \frac{27 - 8}{27} = \frac{3^{3} - 2^{3}}{3^{3}} \\ a_{4} & = \frac{65}{81} = \frac{81 - 16}{81} = \frac{3^{4} - 2^{4}}{3^{4}} \\ ⋮ \end{matrix}$

So we assert $a_{n} = \frac{3^{n} - 2^{n}}{3^{n}}$ for all $n \in ℕ_{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{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} = \frac{3^{n} - 2^{n}}{3^{n}}$ for all $n \in ℕ$ (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}} = [\frac{3^{n}}{3^{n}} - \frac{2^{n}}{3^{n}}] \underset{theorems}{\overset{limit}{=}} 1 - lim_{n \to \infty} {(\frac{2}{3})}^{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 ℕ_{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{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 ℕ_{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{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 (lim_{n \to \infty} a_{n}) + \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 ℝ$ . 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{matrix} 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{matrix}$

We apply this step $n$ times and get

$\begin{matrix} a_{n} - a_{n - 1} & = - \frac{3}{5} (a_{n - 1} - a_{n - 2}) \\ = {(- \frac{3}{5})}^{2} (a_{n - 2} - a_{n - 3}) \\ \dots \\ = {(- \frac{3}{5})}^{n - 1} (a_{1} - a_{0}) \\ = {(- \frac{3}{5})}^{n - 1} (b - a) \end{matrix}$

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} ⟺ a_{n} = a_{0} + \sum_{k = 1}^{n} (a_{k} - a_{k - 1})$

and get a geometric series:

$\begin{matrix} a_{n} = a_{0} + \sum_{k = 1}^{n} {(- \frac{3}{5})}^{k - 1} (b - a) = a + (b - a) \sum_{k = 0}^{n - 1} {(- \frac{3}{5})}^{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 + \frac{5}{8} (b - a) (1 - (- \frac{3}{5})^{n}) \end{matrix}$

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

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

Exercise (Monotonicity criterion for sequences)

Show the sequence $(a_{n})_{n \in ℕ}$ defined by the recursion relation $a_{1} = 1, a_{n + 1} = \sqrt{1 + a_{n}}$ converges to the so-called golden ratio $g = \frac{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 ℕ}$ is monotone and bounded (then, the monotonicity criterion can be applied).

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

$\begin{matrix} 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} \end{matrix}$

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 = \frac{1 + \sqrt{5}}{2}$ , so any number greater than $g$ will be an upper bound. Since $g = \frac{1 + \sqrt{5}}{2} \leq \frac{1 + \sqrt{9}}{2} = \frac{1 + 3}{2} = \frac{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 ℕ$ .

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{.} is monotone}{\overset{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 ℕ$ .

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{.} is monotone}{\overset{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} = \frac{1 + \sqrt{5}}{2}$ and $x_{2} = \frac{1 - \sqrt{5}}{2}$ . Which one is the limit? There is $x_{2} = \frac{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} = \frac{1 + \sqrt{5}}{2} = g$ .

Exercise (Monotonicity criterion for sequences)

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

$1 \leq a_{n} \leq 2$ for all $n \in ℕ$
The subsequence $(a_{2 k - 1})_{k \in ℕ}$ is monotonically increasing and the subsequence $(a_{2 k})_{k \in ℕ}$ 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{assumption}{\overset{induction}{\leq}} 1 + \underset{0 \leq \dots \leq 1}{\underset{⏟}{\frac{1}{a_{n}}}} = a_{n + 1} = \underset{assumption}{\overset{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_{2 k + 1} \geq a_{2 k - 1}$ for all $k \in ℕ$ .

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_{2 k + 3} = 1 + \frac{1}{a_{2 k + 2}} = 1 + \frac{1}{1 + \frac{1}{a_{2 k + 1}}} \underset{assumption}{\overset{induction}{\geq}} 1 + \frac{1}{1 + \frac{1}{a_{2 k - 1}}} = 1 + \frac{1}{a_{2 k}} = a_{2 k + 1}$

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

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_{2 k + 4} = 1 + \frac{1}{a_{2 k + 3}} = 1 + \frac{1}{1 + \frac{1}{a_{2 k + 2}}} \underset{assumption}{\overset{induction}{\leq}} 1 + \frac{1}{1 + \frac{1}{a_{2 k}}} = 1 + \frac{1}{a_{2 k + 1}} = a_{2 k + 2}$

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

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

$\begin{matrix} \tilde{a} = lim_{k \to \infty} a_{2 k - 1} = lim_{k \to \infty} (1 + \frac{1}{a_{2 k - 2}}) = lim_{k \to \infty} (1 + \frac{1}{1 + \frac{1}{a_{2 k - 3}}}) = (1 + \frac{1}{1 + \frac{1}{\tilde{a}}}) \\ ⟺ & \tilde{a} = (1 + \frac{1}{\frac{\tilde{a} + 1}{\tilde{a}}}) = (1 + \frac{\tilde{a}}{\tilde{a} + 1}) = \frac{2 \tilde{a} + 1}{\tilde{a} + 1} \\ ⟺ & {\tilde{a}}^{2} + \tilde{a} = 2 \tilde{a} + 1 \\ ⟺ & {\tilde{a}}^{2} - \tilde{a} - 1 = 0 \end{matrix}$

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_{2 k - 1} > 0$ . So the latter solution must be the limit: $lim_{k \to \infty} a_{2 k - 1} = \tilde{a} = \frac{1 + \sqrt{5}}{2} = g \geq 0$ .

Analogously, $lim_{k \to \infty} a_{2 k} = 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 $(\frac{a_{1} + a_{2} + \dots + a_{n}}{n})$ converges to $a$ .
Does the converse also hold true? I.e. if there is $\frac{a_{1} + a_{2} + \dots + a_{n}}{n} \to a$ does this imply $a_{n} \to a$ ?
Use step 1 to show: $lim_{n \to \infty} \frac{1 + \frac{1}{2} + \dots + \frac{1}{n}}{n} = 0$ .

Solution (Cauchy's limit theorem)

Since $(a_{n})$ converges to $a$ , for any $ϵ > 0$ there must be an $N \in ℕ$ such that for all $n \geq N$ there is:
$| a_{n} - a | < \frac{ϵ}{2}$
But now, the sequence of means $(\frac{(a_{1} - a) + (a_{2} - a) + \dots + (a_{N_{1}} - a)}{n})$ in $N_{1}$ will be dominated by terms $\frac{ϵ}{2}$ if $N_{1}$ is much larger than $N$ . So for a large enough $N_{1}$ , the mean drops below $ϵ$ . This can be done with even smaller $ϵ$ , so for $N_{1} \geq N_{2}$ , there is even:
$| \frac{(a_{1} - a) + (a_{2} - a) + \dots + (a_{N_{1}} - a)}{n} | < \frac{ϵ}{2}$
For $n \geq max {N, N_{2}}$ there is now
$\begin{matrix} | \frac{a_{1} + a_{2} + \dots + a_{n}}{n} - a | \\ = | \frac{a_{1} + a_{2} + \dots + a_{n}}{n} - \frac{n a}{a} | \\ = | \frac{a_{1} + a_{2} + \dots + a_{n} - n a}{n} | \\ = | \frac{a_{1} + a_{2} + \dots + a_{n} - (\overset{n times}{\overset{⏞}{a + a + \dots + a}})}{n} | \\ = | \frac{(a_{1} - a) + (a_{2} - a) + \dots + (a_{n} - a)}{n} | \\ \leq \overset{< \frac{ϵ}{2}}{\overset{⏞}{| \frac{(a_{1} - a) + (a_{2} - a) + \dots + (a_{N} - a)}{n} |}} + | \frac{(a_{N + 1} - a) + (a_{N + 2} - a) + \dots + (a_{n} - a)}{n} | \\ < \frac{ϵ}{2} + \frac{\overset{< \frac{ϵ}{2}}{\overset{⏞}{| a_{N + 1} - a |}} + \overset{\frac{ϵ}{2}}{\overset{⏞}{| a_{N + 2} - a |}} + \dots + \overset{< \frac{ϵ}{2}}{\overset{⏞}{| a_{n} - a |}}}{n} \\ < \frac{ϵ}{2} + \frac{(n - N) \frac{ϵ}{2}}{n} \\ < \frac{ϵ}{2} + \frac{n \frac{ϵ}{2}}{n} = \frac{ϵ}{2} + \frac{ϵ}{2} = ϵ \end{matrix}$
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} + \dots + a_{n}}{n} = \frac{- 1 + 1 - \dots + (- 1)^{n}}{n} = {\begin{matrix} - \frac{1}{n} & for odd n, \\ \frac{0}{n} = 0 & for even n \end{matrix} .$
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_{n \to \infty} \frac{1 + \frac{1}{2} + \dots + \frac{1}{n}}{n} = 0$ .

Subsequences, Accumulation points and Cauchy sequences →

Feedback? Do you want to join?

If you have questions concerning the content, or didn't understand something, the feel free to contact us! We would love to answer your questions! Also we are thankful for critics and/or comments! If you share our vision to explain university math in an comprehensible way, then contact us under:

E-Mail: en@serlo.org

E-Mail: hochschulmathematik@serlo.org

This article is licensed under the free license CC-BY-SA 3.0. With that you can use it, modify it or share it freely, as long as you name „Serlo“ as source and put you changes under the same CC-BY-SA 3.0 oder an compatible license. On the page „Kopier uns!“ we explain you what you have to pay attention to, when using our texts, picture or videos.