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.
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.
), 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:
- 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.
- 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?
Exercise (Finding the limit of a recursively defined sequence)
Let
be recursively defined by:
Prove that this sequence converges and compute the limit by
- finding an explicit form of the sequence
- 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
Exercise (Proving convergence of a recursively defined sequence)
We consider the following recursive sequence
- Prove that this sequence converges and determine the limit.
- 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. 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:
Proof (Heron's method)
In order to show that
really converges to
, we will show that:
converges by the monotony criterion.
- 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.
Proof step: The sequence
is monotonously decreasing.
So
is bounded from below and monotonously decreasing. Hence, it converges by means of the monotony criterion.
Proof step: The limit of
is
.
Hint
The initial value
can be chosen to be any (strictly) positive real number. The proof of convergence works exactly the same way.