Math for Non-Geeks/How to prove convergence for recursive sequences

{{#invoke:Math for Non-Geeks/Seite|oben}}

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

Problem setting

We want to solve problems of the following kind:

Applying the epsilon-criterion is complicated, here: it is not a priori known how elements with large indices look like (e.g. $a_{1000}$), which makes it hard to guess a limit $a$. It is even harder to give a bound for $|a-a_n|$, as the explicit form of $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 $a_n$. Then it can be easier to determine a limit $a$ and prove convergence.
2. Using the monotonicity 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 $(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:

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

The denominator suspiciously looks like a power of $2$ . The enumerator seems to be always one less than the denominator: Template:Math

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

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

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

So we indeed proved $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 $\underset{n\to \mathrm{\infty }}{\lim }{\left(\frac{1}{2}\right)}^n=0$ and we can use the limit theorems:

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 $a_n$ using telescoping sums. To illustrate this, we consider:

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

Applying this step again yields

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

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

The right-hand side is a geometric sum

This allows for an explicit expression

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

Using the monotonicity criterion

Step 1: Proving convergence

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

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

Which seems to be monotonically increasing and bounded by $1$.

Monotonicity is proven inductively. Clearly $a_1\ge a_0$, as

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

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

Hence, $(a_n{)}_{n\in \mathbb{N}}$ is bounded from above by $1$ . Now, the monotonicity criterion can be applied: The sequence is monotonically 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 $a\in ℝ$ with $\underset{n\to \mathrm{\infty }}{\lim }{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 $a=\underset{n\to \mathrm{\infty }}{\lim }{a}_{n+1}$:

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

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

Application: computing roots by Heron's method

The first sequence elements when computing $\sqrt{2}$ starting at $x_0=2$, $x_0=4$ or $x_0=8$.

The sequence elements of Heron's method for $\sqrt{2}$ when starting at $a_0=\frac{1}{4}$.

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

Exercise

{{#invoke:Math for Non-Geeks/Seite|unten}}