How to prove convergence for recursive sequences – Serlo

This article shows you how to prove convergence for recursively defined sequences, i.e. if there is only given and it is not known, what explicitly looks like. The monotony criterion will turn out very useful for this.

Problem setting Bearbeiten

We want to solve problems of the following kind:

Let   be a sequence defined by   and   . 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.  ), which makes it hard to guess a limit  . It is even harder to give a bound for  , as the explicit form of   is often not known.

Problem solving strategies Bearbeiten

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  . Then it can be easier to determine a limit   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 Bearbeiten

One way to prove convergence is to try to find an explicit form for the sequence elements   . 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   converges to 1. Let us try to find an explicit form, i.e. a map  . That means, we are looking for a term   with:

 

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

 

That would mean,   . 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   may perfectly serve as an induction step. The induction starts with

 

The induction step from   to   is done using the recursion relation:

 

So we indeed proved   . This explicit form allows us to use the usual tools (from the previous articles) for proving convergence. For instance, we know   and we can use the limit theorems:

 

Alternative way: using a telescoping sum Bearbeiten

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

 

The difference between two sequence elements   and   is

 

Applying this step again yields

 

So each time, we get an additional factor of   . After   steps, there will be

 

This is not yet an explicit for for  , but for the differences  . However, we can express   using telescoping sums:

 

The right-hand side is a geometric sum

 

This allows for an explicit expression

 

Using   and the limit theorems, we get

 

Using the monotony criterion Bearbeiten

Step 1: Proving convergence Bearbeiten

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:

 

Which seems to be monotonously increasing and bounded by  .

Monotony is proven inductively. Clearly  , as

 

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

 

This establishes monotony of the sequence. Boundedness by   can also be shown inductively. Of course,   which is smaller than 1. In the induction step, we need to show that if   , then also   stays smaller or equal 1:

 

Hence,   is bounded from above by   . 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 Bearbeiten

The convergence above can be used for finding the limit. By step 1, we already know that there must be a limit   with   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  :

 

So if there is any   , it must fulfil   . We resolve the equation for   and get

 

So   is indeed the limit of the sequence  .

Question: Above, we used that if   is known, then there is also   . Why is this the case?

  is the limit of the sequence  . This is just a subsequence of  , which contains all but the first element. Since each subsequence converges to the same limit as the original one, we have  .

Exercises Bearbeiten

Exercise 1 Bearbeiten

Exercise (Finding the limit of a recursively defined sequence)

Let   be recursively defined by:

 

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

 

So we assert that   for all   The proof goes by induction after  :

Theorem whose validity shall be proven for the  :

 

1. Base case:

For   let  .

1. inductive step:

2a. inductive hypothesis:

 

2b. induction theorem:

 

2b. proof of induction step:

 

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

 

Solution sub-exercise 2:

At first, we show that   is monotonously decreasing, i.e.   for all  . This is done by induction over  :

Theorem whose validity shall be proven for the  :

 

1. Base case:

 

1. inductive step:

2a. inductive hypothesis:

 

2b. induction theorem:

 

2b. proof of induction step:

 

In addition,   is bounded from below by   , i.e.   for all  . This is also shown using induction:

Theorem whose validity shall be proven for the  :

 

1. Base case:

 

1. inductive step:

2a. inductive hypothesis:

 

2b. induction theorem:

 

2b. proof of induction step:

 

The monotony criterion then yields convergence of   and there is  . We can get the limit by taking the recursion relation and resolving it for  :

 

Hence,   converges to  .

Übungsaufgabe 2 Bearbeiten

Exercise (Proving convergence of a recursively defined sequence)

We consider the following recursive sequence

 
  1. Prove that this sequence converges and determine the limit.
  2. What happens with  , concerning convergence?

Solution (Proving convergence of a recursively defined sequence)

Solution sub-exercise 1:

There is

 

Applying this step   times, we get

 

We use telescoping sums

 

and obtain

 

So we have an explicit form. With   and the limit theorems, we get the limit

 

Solution sub-exercise 2:

For   and   we can plug in

 

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  :

 

1. Base case:

We start with  . As above,   and   renders  .

1. inductive step:

2a. inductive hypothesis:

 

2b. induction theorem:

 

2b. proof of induction step:

 

Hence, the sequence is constantly 1 and its limit is  .

Application: computing roots by Heron's method Bearbeiten

 
The first sequence elements when computing   starting at  ,   or  .
 
The sequence elements of Heron's method for   when starting at  .

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  . It recursively constructs a sequence of better and better approximations for the root   . That these approximation get increasingly better is fixed within a theorem:

Theorem (Heron's method)

Let   be a real number with  . Let the sequence   be recursively defined by

 

Then,   converges to  .

Sequence elements of   yield an increasingly precise approximation for  , where we can get to an arbitrary precision   . One can, for instance, use a computer to approximate   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   really converges to   , we will show that:

  1.   converges by the monotony criterion.
  2. The limit of   is   .

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   converges.

We prove that   is monotonously decreasing and bounded from below.

Proof step: The sequence   is bounded from below.

A bound is established using the inequality between arithmetic and geometric means: For   there is  . Hence,

 

So   is bounded from below by  .

Proof step: The sequence   is monotonously decreasing.

This means, we need to show   , or equivalently,  :

 

So   is bounded from below and monotonously decreasing. Hence, it converges by means of the monotony criterion.

Proof step: The limit of   is  .

We will make use of a trick, here: As   converges, there must be a limit   , i.e. a real number with  . Then, there is also  , since   is a subsequence of   . The recursion relation and the limit theorems yield:

 

This can be resolved for   and we get the limit:

 

At this point, there are two candidates for the limit. But since   , we also have   so the convergence must be towards the positive limit candidate

 

Hint

The initial value   can be chosen to be any (strictly) positive real number. The proof of convergence works exactly the same way.

Exercise Bearbeiten

Exercise (Recursion for the third root)

Let   with  . Show that the sequence defined recursively for   via

 

converges to   Proceed as follows:

  1. Use Bernoulli's inequality: For every   with   there is   and use this to show by induction that   for all  
  2. Use step 1 to show:   is monotonously decreasing and bounded from below.
  3. Determine the limit of  .

Solution (Recursion for the third root)

  1. First inequality: At first,
     

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

     

    So with   we get:

     

    Second inequality: Induction on  :

    Induction basis:  .   holds by assumption.

    Induction step:  .   by the first inequality, since there is   by the induction assumption.

  2.   is monotonously decreasing: There is
     

      is bounded from below: Since   we directly obtain

     
  3. As   is monotonously decreasing and bounded from below, the monotony criterion implies its convergence. We denote the limit by  . We plug this into the recursive relation and resolve for  :
     

Hint

We can even compute roots of higher order: For any natural number   , as well as for real numbers   and   we can recursively construct a sequence   with

 

and show that it converges to   .