How to prove convergence for recursive sequences – Serlo

Zur Navigation springen Zur Suche springen

This article shows you how to prove convergence for recursively defined sequences, i.e. if there is only ${\displaystyle a_{n+1}=f(a_{n})}$ given and it is not known, what ${\displaystyle a_{n}}$ explicitly looks like. The monotony criterion will turn out very useful for this.

Problem setting

We want to solve problems of the following kind:

Let ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ be a sequence defined by ${\displaystyle a_{0}=0}$ and ${\displaystyle a_{n+1}={\tfrac {1}{2}}a_{n}+{\tfrac {1}{2}}}$ . Does it converge? If yes, what is its limit value?

Applying the epsilon-criterion is complicated, here: it is not a priori known how elements with large indices look like (e.g. ${\displaystyle a_{1000}}$), which makes it hard to guess a limit ${\displaystyle a}$. It is even harder to give a bound for ${\displaystyle |a-a_{n}|}$, as the explicit form of ${\displaystyle a_{n}}$ is often not known.

Problem solving strategies

The article will cover two strategies for proving convergence of a recursively defined sequence:

1. Finding the explicit form: You may try to find the explicit for of the sequence elements ${\displaystyle a_{n}}$. Then it can be easier to determine a limit ${\displaystyle a}$ and prove convergence.
2. Using the monotony criterion: If you can not find an explicit form, but you are convinced that the sequence should converge, you may try to use this criterion. It works without knowing an explicit form.

Finding the explicit form

One way to prove convergence is to try to find an explicit form for the sequence elements ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ . It is useful, to compute the first sequence elements in order to get a feeling of how the sequence behaves. In the above example:

{\displaystyle {\begin{aligned}a_{0}&=0\\[0.3em]a_{1}&={\frac {1}{2}}a_{0}+{\frac {1}{2}}={\frac {1}{2}}\cdot 0+{\frac {1}{2}}={\frac {1}{2}}\\[0.3em]a_{2}&={\frac {1}{2}}a_{1}+{\frac {1}{2}}={\frac {1}{2}}\cdot {\frac {1}{2}}+{\frac {1}{2}}={\frac {3}{4}}\\[0.3em]a_{3}&={\frac {1}{2}}a_{2}+{\frac {1}{2}}={\frac {1}{2}}\cdot {\frac {3}{4}}+{\frac {1}{2}}={\frac {7}{8}}\\[0.3em]a_{4}&={\frac {1}{2}}a_{3}+{\frac {1}{2}}={\frac {1}{2}}\cdot {\frac {7}{8}}+{\frac {1}{2}}={\frac {15}{16}}\\[0.3em]&\vdots \end{aligned}}}

These elemnts are all smaller than 1, while slowly approaching it. We therefore assert that ${\displaystyle a_{n}}$ converges to 1. Let us try to find an explicit form, i.e. a map ${\displaystyle n\mapsto a_{n}}$. That means, we are looking for a term ${\displaystyle f(x)}$ with:

{\displaystyle {\begin{aligned}f(0)&=0\\[0.3em]f(1)&={\frac {1}{2}}\\[0.3em]f(2)&={\frac {3}{4}}\\[0.3em]f(3)&={\frac {7}{8}}\\[0.3em]&\vdots \end{aligned}}}

The denominator suspiciously looks like a power of ${\displaystyle 2}$ . The enumerator seems to be always one less than the denominator:

{\displaystyle {\begin{aligned}{\begin{array}{rll}f(0)&=0&={\frac {2^{0}-1}{2^{0}}}\\[0.3em]f(1)&={\frac {1}{2}}&={\frac {2^{1}-1}{2^{1}}}\\[0.3em]f(2)&={\frac {3}{4}}&={\frac {2^{2}-1}{2^{2}}}\\[0.3em]f(3)&={\frac {7}{8}}&={\frac {2^{3}-1}{2^{3}}}\\[0.3em]&\vdots \end{array}}\end{aligned}}}

That would mean, ${\displaystyle f(n)={\frac {2^{n}-1}{2^{n}}}}$ . So we assert that

${\displaystyle a_{n}=f(n)={\frac {2^{n}-1}{2^{n}}}=1-{\frac {1}{2^{n}}}=1-\left({\frac {1}{2}}\right)^{n}}$

Now, we should try to prove or disprove this assertion. Induction is a suitable way to do this, as the recursion relation ${\displaystyle a_{n+1}={\tfrac {1}{2}}a_{n}+{\tfrac {1}{2}}}$ may perfectly serve as an induction step. The induction starts with

${\displaystyle a_{0}=0=1-1=1-\left({\frac {1}{2}}\right)^{0}}$

The induction step from ${\displaystyle n}$ to ${\displaystyle n+1}$ is done using the recursion relation:

{\displaystyle {\begin{aligned}a_{n+1}&={\frac {1}{2}}{\color {Teal}a_{n}}+{\frac {1}{2}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{induction assumption}}\right.}\\[0.3em]&={\frac {1}{2}}\cdot {\color {Teal}\left(1-\left({\frac {1}{2}}\right)^{n}\right)}+{\frac {1}{2}}\\[0.3em]&={\frac {1}{2}}-\left({\frac {1}{2}}\right)^{n+1}+{\frac {1}{2}}\\[0.3em]&=1-\left({\frac {1}{2}}\right)^{n+1}\end{aligned}}}

So we indeed proved ${\displaystyle a_{n}=1-\left({\frac {1}{2}}\right)^{n}}$ . This explicit form allows us to use the usual tools (from the previous articles) for proving convergence. For instance, we know ${\displaystyle \lim _{n\to \infty }\left({\frac {1}{2}}\right)^{n}=0}$ and we can use the limit theorems:

{\displaystyle {\begin{aligned}\lim _{n\to \infty }a_{n}&=\lim _{n\to \infty }1-\left({\frac {1}{2}}\right)^{n}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{Limit theorems: }}\lim _{n\to \infty }(a_{n}+b_{n})=\lim _{n\to \infty }a_{n}+\lim _{n\to \infty }b_{n}\right.}\\[0.3em]&=\lim _{n\to \infty }1-\lim _{n\to \infty }\left({\frac {1}{2}}\right)^{n}\\[0.3em]&=1-0=1\end{aligned}}}

Alternative way: using a telescoping sum

Sometimes, finding a simple explicit form may be enormously hard or even impossible. In any case, one can write the elements ${\displaystyle a_{n}}$ using telescoping sums. To illustrate this, we consider:

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

The difference between two sequence elements ${\displaystyle a_{n}}$ and ${\displaystyle a_{n-1}}$ is

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

Applying this step again yields

{\displaystyle {\begin{aligned}a_{n}-a_{n-1}&=-{\frac {1}{2}}(a_{n-1}-a_{n-2})\\&=-{\frac {1}{2}}\left({\frac {1}{2}}a_{n-2}+{\frac {1}{2}}a_{n-3}-a_{n-2}\right)\\&=-{\frac {1}{2}}\left({\frac {1}{2}}a_{n-3}-{\frac {1}{2}}a_{n-2}\right)\\&=\left(-{\frac {1}{2}}\right)^{2}(a_{n-2}-a_{n-3})\end{aligned}}}

So each time, we get an additional factor of ${\displaystyle -{\tfrac {1}{2}}}$ . After ${\displaystyle n-1}$ steps, there will be

${\displaystyle a_{n}-a_{n-1}=\left(-{\frac {1}{2}}\right)^{n-1}\underbrace {(a_{1}-a_{0})} _{=1}=\left(-{\frac {1}{2}}\right)^{n-1}}$

This is not yet an explicit for for ${\displaystyle a_{n}}$, but for the differences ${\displaystyle a_{n}-a_{n-1}}$. However, we can express ${\displaystyle a_{n}}$ using telescoping sums:

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

The right-hand side is a geometric sum

${\displaystyle \sum _{k=1}^{n}\left(-{\frac {1}{2}}\right)^{k-1}=\sum _{k=0}^{n-1}\left(-{\frac {1}{2}}\right)^{k}={\frac {1-(-{\frac {1}{2}})^{n}}{1-(-{\frac {1}{2}})}}={\frac {1-(-{\frac {1}{2}})^{n}}{\frac {3}{2}}}={\tfrac {2}{3}}(1-(-{\tfrac {1}{2}})^{n})}$

This allows for an explicit expression

${\displaystyle a_{n}={\tfrac {2}{3}}(1-(-{\tfrac {1}{2}})^{n})}$

Using ${\displaystyle \lim _{n\to \infty }(-{\tfrac {1}{2}})^{n}=0}$ and the limit theorems, we get

${\displaystyle \lim _{n\to \infty }a_{n}=\lim _{n\to \infty }{\tfrac {2}{3}}(1-(-{\tfrac {1}{2}})^{n})={\tfrac {2}{3}}(1-0)={\tfrac {2}{3}}}$

Using the monotony criterion

Step 1: Proving convergence

What if we cannot find an explicit form of the sequence elements? If the sequence is monotonously increasing or decreasing, the monotony criterion can be useful. We recall this criterion:

All bounded and monotonous functions converge.

Hence, it suffices to show boundedness and monotony of the sequence. For instance, in the above case:

{\displaystyle {\begin{aligned}a_{0}&=0\\[0.3em]a_{1}&={\frac {1}{2}}a_{0}+{\frac {1}{2}}={\frac {1}{2}}\cdot 0+{\frac {1}{2}}={\frac {1}{2}}\\[0.3em]a_{2}&={\frac {1}{2}}a_{1}+{\frac {1}{2}}={\frac {1}{2}}\cdot {\frac {1}{2}}+{\frac {1}{2}}={\frac {3}{4}}\\[0.3em]a_{3}&={\frac {1}{2}}a_{2}+{\frac {1}{2}}={\frac {1}{2}}\cdot {\frac {3}{4}}+{\frac {1}{2}}={\frac {7}{8}}\\[0.3em]a_{4}&={\frac {1}{2}}a_{3}+{\frac {1}{2}}={\frac {1}{2}}\cdot {\frac {7}{8}}+{\frac {1}{2}}={\frac {15}{16}}\\[0.3em]&\vdots \end{aligned}}}

Which seems to be monotonously increasing and bounded by ${\displaystyle 1}$.

Monotony is proven inductively. Clearly ${\displaystyle a_{1}\geq a_{0}}$, as

${\displaystyle a_{1}={\frac {1}{2}}a_{0}+{\frac {1}{2}}={\frac {1}{2}}\cdot 0+{\frac {1}{2}}={\frac {1}{2}}\geq 0=a_{0}}$

The induction step from ${\displaystyle n}$ to ${\displaystyle n+1}$ consists of showing that the sequence element gets bigger within that step:

{\displaystyle {\begin{aligned}a_{n+1}&={\frac {1}{2}}{\color {Teal}a_{n}}+{\frac {1}{2}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{induction assumption: }}a_{n}\geq a_{n-1}\right.}\\[0.3em]&\geq {\frac {1}{2}}{\color {Teal}a_{n-1}}+{\frac {1}{2}}=a_{n}\end{aligned}}}

This establishes monotony of the sequence. Boundedness by ${\displaystyle 1}$ can also be shown inductively. Of course, ${\displaystyle a_{0}=0}$ which is smaller than 1. In the induction step, we need to show that if ${\displaystyle a_{n}\leq 1}$ , then also ${\displaystyle a_{n+1}\leq 1}$ stays smaller or equal 1:

{\displaystyle {\begin{aligned}a_{n+1}&={\frac {1}{2}}{\color {Teal}a_{n}}+{\frac {1}{2}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{induction assumption: }}a_{n}\leq 1\right.}\\[0.3em]&\leq {\frac {1}{2}}{\color {Teal}1}+{\frac {1}{2}}=1\end{aligned}}}

Hence, ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ is bounded from above by ${\displaystyle 1}$ . Now, the monotony criterion can be applied: The sequence is monotonously increasing and bounded from above, so it must converge.

Step 2: finding the limit

The convergence above can be used for finding the limit. By step 1, we already know that there must be a limit ${\displaystyle a\in \mathbb {R} }$ with ${\displaystyle \lim _{n\to \infty }a_{n}=a}$ and it can be at most the upper bound, namely 1. As the sequence elements approach 1 closer and closer, we assert that it is exactly 1.

To verify this, we take a look at ${\displaystyle a=\lim _{n\to \infty }a_{n+1}}$:

{\displaystyle {\begin{aligned}a&=\lim _{n\to \infty }a_{n+1}\\[0.5em]&{\color {OliveGreen}\left\downarrow \ {\text{recursion relation: }}a_{n+1}={\frac {1}{2}}a_{n}+{\frac {1}{2}}\right.}\\[0.5em]&=\lim _{n\to \infty }{\frac {1}{2}}a_{n}+{\frac {1}{2}}\\[0.5em]&{\color {OliveGreen}\left\downarrow \ {\text{limit theorems}}\right.}\\[0.5em]&=\left(\lim _{n\to \infty }{\frac {1}{2}}\right)\cdot \left(\lim _{n\to \infty }a_{n}\right)+\lim _{n\to \infty }{\frac {1}{2}}\\[0.5em]&={\frac {1}{2}}a+{\frac {1}{2}}\end{aligned}}}

So if there is any ${\displaystyle a}$ , it must fulfil ${\displaystyle a={\tfrac {1}{2}}a+{\tfrac {1}{2}}}$ . We resolve the equation for ${\displaystyle a}$ and get

${\displaystyle a={\frac {1}{2}}a+{\frac {1}{2}}\iff {\frac {1}{2}}a={\frac {1}{2}}\iff a=1}$

So ${\displaystyle a=1}$ is indeed the limit of the sequence ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$.

Question: Above, we used that if ${\displaystyle \lim _{n\to \infty }a_{n}=a}$ is known, then there is also ${\displaystyle \lim _{n\to \infty }a_{n+1}=a}$ . Why is this the case?

${\displaystyle \lim _{n\to \infty }a_{n+1}}$ is the limit of the sequence ${\displaystyle (a_{n+1})_{n\in \mathbb {N} }}$. This is just a subsequence of ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$, which contains all but the first element. Since each subsequence converges to the same limit as the original one, we have ${\displaystyle \lim _{n\to \infty }a_{n+1}=\lim _{n\to \infty }a_{n}=a}$.

Exercises

Exercise 1

Exercise (Finding the limit of a recursively defined sequence)

Let ${\displaystyle a_{n}}$ be recursively defined by:

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

Prove that this sequence converges and compute the limit by

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

Solution (Finding the limit of a recursively defined sequence)

Solution sub-exercise 1:

There is

{\displaystyle {\begin{aligned}a_{0}&=2\\[0.3em]a_{1}&=2-{\frac {1}{2}}={\frac {3}{2}}\\[0.3em]a_{2}&=2-{\frac {1}{\frac {3}{2}}}=2-{\frac {2}{3}}={\frac {4}{3}}\\[0.3em]a_{3}&=2-{\frac {1}{\frac {4}{3}}}=2-{\frac {3}{4}}={\frac {5}{4}}\\[0.3em]&\vdots \end{aligned}}}

So we assert that ${\displaystyle a_{n}={\frac {n+2}{n+1}}}$ for all ${\displaystyle n\in \mathbb {N} }$ The proof goes by induction after ${\displaystyle n}$:

Theorem whose validity shall be proven for the ${\displaystyle n\in \mathbb {N} }$:

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

1. Base case:

For ${\displaystyle n=0}$ let ${\displaystyle a_{0}={\tfrac {0+2}{0+1}}=2}$.

1. inductive step:

2a. inductive hypothesis:

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

2b. induction theorem:

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

2b. proof of induction step:

{\displaystyle {\begin{aligned}a_{n+1}&=2-{\frac {1}{a_{n}}}{\overset {\text{IV}}{=}}2-{\tfrac {1}{\frac {n+2}{n+1}}}\\[0.5em]&=2-{\frac {n+1}{n+2}}={\frac {2n+4}{n+2}}-{\frac {n+1}{n+2}}={\frac {n+3}{n+2}}\end{aligned}}}

So we have an explicit form. The limit theorems now directly yield the solution

${\displaystyle \lim _{n\to \infty }a_{n}=\lim _{n\to \infty }{\frac {n+2}{n+1}}=\lim _{n\to \infty }{\frac {1+{\frac {2}{n}}}{1+{\frac {1}{n}}}}={\frac {1}{1}}=1}$

Solution sub-exercise 2:

At first, we show that ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ is monotonously decreasing, i.e. ${\displaystyle a_{n+1}\leq a_{n}}$ for all ${\displaystyle n\in \mathbb {N} }$. This is done by induction over ${\displaystyle n}$:

Theorem whose validity shall be proven for the ${\displaystyle n\in \mathbb {N} }$:

${\displaystyle a_{n+1}\leq a_{n}}$

1. Base case:

${\displaystyle a_{1}=2-{\frac {1}{a_{0}}}=2-{\frac {1}{2}}={\frac {3}{2}}\leq 2=a_{0}}$

1. inductive step:

2a. inductive hypothesis:

${\displaystyle a_{n+1}\leq a_{n}}$

2b. induction theorem:

${\displaystyle a_{n+2}\leq a_{n+1}}$

2b. proof of induction step:

${\displaystyle a_{n+2}=2-{\frac {1}{a_{n+1}}}{\overset {\text{IV}}{\leq }}2-{\frac {1}{a_{n}}}=a_{n+1}}$

In addition, ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ is bounded from below by ${\displaystyle 1}$ , i.e. ${\displaystyle a_{n}\geq 1}$ for all ${\displaystyle n\in \mathbb {N} }$. This is also shown using induction:

Theorem whose validity shall be proven for the ${\displaystyle n\in \mathbb {N} }$:

${\displaystyle a_{n}\geq 1}$

1. Base case:

${\displaystyle a_{0}=2\geq 1}$

1. inductive step:

2a. inductive hypothesis:

${\displaystyle a_{n}\geq 1}$

2b. induction theorem:

${\displaystyle a_{n+1}\geq 1}$

2b. proof of induction step:

${\displaystyle a_{n+1}=2-{\frac {1}{a_{n}}}{\overset {\text{IV}}{\geq }}2-{\frac {1}{1}}=2-1=1}$

The monotony criterion then yields convergence of ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ and there is ${\displaystyle \lim _{n\to \infty }a_{n}=a=\lim _{n\to \infty }a_{n+1}}$. We can get the limit by taking the recursion relation and resolving it for ${\displaystyle a}$:

{\displaystyle {\begin{aligned}&\underbrace {\lim _{n\to \infty }a_{n}} _{=a}=\lim _{n\to \infty }2-{\frac {1}{a_{n}}}=2-{\frac {1}{\lim _{n\to \infty }a_{n}}}=2-{\frac {1}{a}}\\[0.3em]\iff &a^{2}=2a-1\\[0.3em]\iff &\underbrace {a^{2}-2a+1} _{=(a-1)^{2}}=0\\[0.3em]\iff &a=1\end{aligned}}}

Hence, ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ converges to ${\displaystyle a=1}$.

Übungsaufgabe 2

Exercise (Proving convergence of a recursively defined sequence)

We consider the following recursive sequence

{\displaystyle {\begin{aligned}a_{0}&=0\\a_{1}&=2\\a_{n}&={\frac {1}{3}}a_{n-1}+{\frac {2}{3}}a_{n-2}\end{aligned}}}
1. Prove that this sequence converges and determine the limit.
2. What happens with ${\displaystyle a_{0}=a_{1}=1}$, concerning convergence?

Solution (Proving convergence of a recursively defined sequence)

Solution sub-exercise 1:

There is

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

Applying this step ${\displaystyle n}$ times, we get

{\displaystyle {\begin{aligned}a_{n}-a_{n-1}&=-{\frac {2}{3}}(a_{n-1}-a_{n-2})\\&=\left(-{\frac {2}{3}}\right)^{2}(a_{n-2}-a_{n-3})\\&=\ldots \\&=\left(-{\frac {2}{3}}\right)^{n-1}\underbrace {(a_{1}-a_{0})} _{=2}\\&=2\cdot \left(-{\frac {2}{3}}\right)^{n-1}\end{aligned}}}

We use telescoping sums

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

and obtain

{\displaystyle {\begin{aligned}a_{n}&=\sum _{k=1}^{n}(a_{k}-a_{k-1})\\&=2\cdot \sum _{k=1}^{n}\left(-{\frac {2}{3}}\right)^{k-1}\\&=2\cdot \sum _{k=0}^{n-1}\left(-{\frac {2}{3}}\right)^{k}\\&=2\cdot {\frac {1-(-{\frac {2}{3}})^{n}}{1-(-{\frac {2}{3}})}}\\&=2\cdot {\frac {1-(-{\frac {2}{3}})^{n}}{\frac {5}{3}}}\\&=2\cdot {\tfrac {3}{5}}(1-(-{\tfrac {2}{3}})^{n})\\&={\tfrac {6}{5}}\cdot (1-(-{\tfrac {2}{3}})^{n})\end{aligned}}}

So we have an explicit form. With ${\displaystyle \lim _{n\to \infty }(-{\tfrac {2}{3}})^{n}=0}$ and the limit theorems, we get the limit

${\displaystyle \lim _{n\to \infty }a_{n}=\lim _{n\to \infty }{\frac {6}{5}}(1-(-{\frac {2}{3}})^{n})={\frac {6}{5}}(1-0)={\frac {6}{5}}}$

Solution sub-exercise 2:

For ${\displaystyle a_{0}=1}$ and ${\displaystyle a_{1}=1}$ we can plug in

${\displaystyle a_{2}={\frac {1}{3}}\cdot 1+{\frac {2}{3}}\cdot 1=1}$

The next plugging-ins would exactly look the same and we always get 1. So we assert that the sequence is constantly 1 and therefore converges to 1. We prove this assertion by induction

Theorem whose validity shall be proven for the ${\displaystyle n\in \mathbb {N} }$:

${\displaystyle a_{n}=1}$

1. Base case:

We start with ${\displaystyle n=2}$. As above, ${\displaystyle a_{0}=1}$ and ${\displaystyle a_{1}=1}$ renders ${\displaystyle a_{2}=1}$.

1. inductive step:

2a. inductive hypothesis:

${\displaystyle a_{n}=1}$

2b. induction theorem:

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

2b. proof of induction step:

${\displaystyle a_{n+1}={\frac {1}{3}}\cdot a_{n}+{\frac {2}{3}}a_{n-1}{\overset {\text{IV}}{=}}{\frac {1}{3}}\cdot 1+{\frac {2}{3}}\cdot 1=1}$

Hence, the sequence is constantly 1 and its limit is ${\displaystyle \lim _{n\to \infty }a_{n}=\lim _{n\to \infty }1=1}$.

Application: computing roots by Heron's method

The first sequence elements when computing ${\displaystyle {\sqrt {2}}}$ starting at ${\displaystyle x_{0}=2}$, ${\displaystyle x_{0}=4}$ or ${\displaystyle x_{0}=8}$.
The sequence elements of Heron's method for ${\displaystyle {\sqrt {2}}}$ when starting at ${\displaystyle a_{0}={\tfrac {1}{4}}}$.

We will now come to an application, where convergence of a recursively defined sequence can be shown using the monotony criterion: Heron's method can be used to compute roots of integers, rational or even real numbers ${\displaystyle a}$. It recursively constructs a sequence of better and better approximations for the root ${\displaystyle {\sqrt {a}}}$ . That these approximation get increasingly better is fixed within a theorem:

Theorem (Heron's method)

Let ${\displaystyle a}$ be a real number with ${\displaystyle a>0}$. Let the sequence ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ be recursively defined by

{\displaystyle {\begin{aligned}x_{0}&=a\\x_{n+1}&={\frac {1}{2}}\left(x_{n}+{\frac {a}{x_{n}}}\right)\end{aligned}}}

Then, ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ converges to ${\displaystyle {\sqrt {a}}}$.

Sequence elements of ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ yield an increasingly precise approximation for ${\displaystyle {\sqrt {a}}}$, where we can get to an arbitrary precision ${\displaystyle \epsilon >0}$ . One can, for instance, use a computer to approximate ${\displaystyle {\sqrt {a}}}$ up to an arbitrary precision, which is done by performing a sufficiently large number of recursion steps.

Proof (Heron's method)

In order to show that ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ really converges to ${\displaystyle {\sqrt {a}}}$ , we will show that:

1. ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ converges by the monotony criterion.
2. The limit of ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ is ${\displaystyle {\sqrt {a}}}$ .

We can not leave out the first step, as in step 2, we use that the sequence converges. A direct proof of convergence using the Epsilon-criterion (in one step) would be way more complicated.

Proof step: The sequence ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ converges.

We prove that ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ is monotonously decreasing and bounded from below.

Proof step: The sequence ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ is bounded from below.

A bound is established using the inequality between arithmetic and geometric means: For ${\displaystyle a,b\geq 0}$ there is ${\displaystyle {\tfrac {a+b}{2}}\geq {\sqrt {ab}}}$. Hence,

{\displaystyle {\begin{aligned}x_{n+1}&={\frac {1}{2}}\left(x_{n}+{\frac {a}{x_{n}}}\right)\\[0.5em]&={\frac {x_{n}+{\frac {a}{x_{n}}}}{2}}\\[0.5em]&\ {\color {OliveGreen}\left\downarrow \ {\frac {a+b}{2}}\geq {\sqrt {ab}}\right.}\\[0.5em]&\geq {\sqrt {x_{n}\cdot {\frac {a}{x_{n}}}}}\\[0.5em]&={\sqrt {a}}.\end{aligned}}}

So ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ is bounded from below by ${\displaystyle {\sqrt {a}}}$.

Proof step: The sequence ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ is monotonously decreasing.

This means, we need to show ${\displaystyle x_{n+1}\leq x_{n}}$ , or equivalently, ${\displaystyle x_{n}-x_{n+1}\geq 0}$:

{\displaystyle {\begin{aligned}x_{n}-x_{n+1}&=x_{n}-{\frac {1}{2}}\left(x_{n}+{\frac {a}{x_{n}}}\right)\\[0.5em]&={\frac {1}{2}}\left(x_{n}-{\frac {a}{x_{n}}}\right)\\[0.5em]&={\frac {1}{2x_{n}}}(x_{n}^{2}-a)\\[0.5em]&\ {\color {OliveGreen}\left\downarrow \ x_{n}\geq {\sqrt {a}}\Rightarrow x_{n}\geq 0\Rightarrow {\frac {1}{2x_{n}}}\geq 0\right.}\\[0.5em]&=\underbrace {\frac {1}{2x_{n}}} _{\geq 0}(x_{n}^{2}-a)\\[0.5em]&\ {\color {OliveGreen}\left\downarrow \ x_{n}\geq {\sqrt {a}}\Rightarrow x_{n}^{2}\geq a\Rightarrow x_{n}^{2}-a\geq 0\right.}\\[0.5em]&=\underbrace {\frac {1}{2x_{n}}} _{\geq 0}\underbrace {(x_{n}^{2}-a)} _{\geq 0}\\&\geq 0.\end{aligned}}}

So ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ is bounded from below and monotonously decreasing. Hence, it converges by means of the monotony criterion.

Proof step: The limit of ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ is ${\displaystyle {\sqrt {a}}}$.

We will make use of a trick, here: As ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ converges, there must be a limit ${\displaystyle x}$ , i.e. a real number with ${\displaystyle x=\lim _{n\to \infty }x_{n}}$. Then, there is also ${\displaystyle \lim _{n\to \infty }x_{n+1}=x}$, since ${\displaystyle (x_{n+1})_{n\in \mathbb {N} }}$ is a subsequence of ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ . The recursion relation and the limit theorems yield:

{\displaystyle {\begin{aligned}x&=\lim _{n\to \infty }x_{n+1}\\[0.3em]&=\lim _{n\to \infty }{\frac {1}{2}}\left(x_{n}+{\frac {a}{x_{n}}}\right)\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{limit theorems}}\right.}\\[0.3em]&={\frac {1}{2}}\left(\lim _{n\to \infty }x_{n}+{\frac {a}{\lim _{n\to \infty }x_{n}}}\right)\\[0.3em]&={\frac {1}{2}}\left(x+{\frac {a}{x}}\right)\end{aligned}}}

This can be resolved for ${\displaystyle x}$ and we get the limit:

{\displaystyle {\begin{aligned}x={\frac {1}{2}}\left(x+{\frac {a}{x}}\right)&\iff x={\frac {x^{2}+a}{2x}}\\[0.5em]&\iff 2x^{2}=x^{2}+a\\[0.5em]&\iff x^{2}=a\\[0.5em]&\iff x=\pm {\sqrt {a}}\end{aligned}}}

At this point, there are two candidates for the limit. But since ${\displaystyle x_{n}\geq 0}$ , we also have ${\displaystyle x\geq 0}$ so the convergence must be towards the positive limit candidate

${\displaystyle \lim _{n\to \infty }x_{n}={\sqrt {a}}}$

Hint

The initial value ${\displaystyle x_{0}}$ can be chosen to be any (strictly) positive real number. The proof of convergence works exactly the same way.

Exercise

Exercise (Recursion for the third root)

Let ${\displaystyle x_{0}\in \mathbb {R} }$ with ${\displaystyle x_{0}^{3}>a\in \mathbb {R} ^{+}}$. Show that the sequence defined recursively for ${\displaystyle n\in \mathbb {N} }$ via

${\displaystyle x_{n+1}=x_{n}-{\frac {x_{n}^{3}-a}{3x_{n}^{2}}}={\frac {1}{3}}\cdot \left(2x_{n}+{\frac {a}{x_{n}^{2}}}\right)}$

converges to ${\displaystyle {\sqrt[{3}]{a}}}$ Proceed as follows:

1. Use Bernoulli's inequality: For every ${\displaystyle x\in \mathbb {R} }$ with ${\displaystyle x^{3}>a}$ there is ${\displaystyle \left(x-{\frac {x^{3}-a}{3x^{2}}}\right)^{3}\geq a}$ and use this to show by induction that ${\displaystyle x_{n}^{3}>a}$ for all ${\displaystyle n\in \mathbb {N} _{0}}$
2. Use step 1 to show: ${\displaystyle (x_{n})_{n\in \mathbb {N} _{0}}}$ is monotonously decreasing and bounded from below.
3. Determine the limit of ${\displaystyle (x_{n})}$.

Solution (Recursion for the third root)

1. First inequality: At first,
${\displaystyle \left(x-{\frac {x^{3}-a}{3x^{2}}}\right)^{3}=\left(x\left(1-{\frac {x^{3}-a}{3x^{3}}}\right)\right)^{3}=x^{3}\left(1-{\frac {x^{3}-a}{3x^{3}}}\right)^{3}}$

Bernoulli's inequality can be applied to the last factor, as

${\displaystyle -{\frac {x^{3}-a}{3x^{3}}}>-1\iff -(x^{3}-a)>-3x^{3}\iff -x^{3}+a>-3x^{3}\iff \underbrace {a} _{>0}>\underbrace {-2x^{3}} _{<-2a<0}}$

So with ${\displaystyle x^{3}>a>0}$ we get:

${\displaystyle x^{3}\left(1-{\frac {x^{3}-a}{3x^{3}}}\right)^{3}\geq x^{3}\left(1-3\cdot {\frac {x^{3}-a}{3x^{3}}}\right)=x^{3}-(x^{3}-a)=a}$

Second inequality: Induction on ${\displaystyle n}$:

Induction basis: ${\displaystyle n=0}$. ${\displaystyle x_{0}^{3}\geq a}$ holds by assumption.

Induction step: ${\displaystyle n\to n+1}$. ${\displaystyle x_{n+1}^{3}=\left(x_{n}-{\frac {x_{n}^{3}-a}{3x_{n}^{2}}}\right)^{3}\geq a}$ by the first inequality, since there is ${\displaystyle x_{n}^{3}>a}$ by the induction assumption.

2. ${\displaystyle (x_{n})}$ is monotonously decreasing: There is
${\displaystyle x_{n+1}-x_{n}=x_{n}-{\frac {x_{n}^{3}-a}{3x_{n}^{2}}}-x_{n}=-{\frac {\overbrace {x_{n}^{3}-a} ^{>0}}{\underbrace {3x_{n}^{2}} _{>0}}}<0}$

${\displaystyle (x_{n})}$ is bounded from below: Since ${\displaystyle x_{n}^{3}\geq a}$ we directly obtain

${\displaystyle x_{n}\geq {\sqrt[{3}]{a}}}$
3. As ${\displaystyle (x_{n})}$ is monotonously decreasing and bounded from below, the monotony criterion implies its convergence. We denote the limit by ${\displaystyle \lim _{n\to \infty }x_{n}=\lim _{n\to \infty }x_{n+1}=x}$. We plug this into the recursive relation and resolve for ${\displaystyle x}$:
${\displaystyle x-{\frac {x^{3}-a}{3x^{2}}}=x\iff {\frac {x^{3}-a}{3x^{2}}}=0\iff x^{3}-a=0\iff x^{3}=a\iff x={\sqrt[{3}]{a}}}$

Hint

We can even compute roots of higher order: For any natural number ${\displaystyle k\geq 2}$ , as well as for real numbers ${\displaystyle x_{0}>0}$ and ${\displaystyle a>0}$ we can recursively construct a sequence ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ with

${\displaystyle x_{n+1}={\frac {1}{k}}\left((k-1)x_{n}-{\frac {a}{x_{n}^{k-1}}}\right)}$

and show that it converges to ${\displaystyle {\sqrt[{k}]{a}}}$ .