Limits of recursive sequences

Printable View

January 25th 2010, 03:14 AM
PJani

Limits of recursive sequences

I am trying to figure out how can i get limit of recursive sequence.
For example this one.
$a_1=1$
$a_{n+1}=\frac{a_n}{2}+1$

Is there any common way of solving all recursive limits?
January 25th 2010, 04:05 AM
HallsofIvy

Quote:

Originally Posted by PJani

I am trying to figure out how can i get limit of recursive sequence.
For example this one.
$a_1=1$
$a_{n+1}=\frac{a_n}{2}+1$

Is there any common way of solving all recursive limits?

IF the limit exists, then take the limit of both sides of the recursion equation: $\lim a_{n+1}= \frac{\lim a_n}{2}+ 1$ . If the limit exists and $\lim a_n= a$ , then both of those limits are a. You get the equation $a= \frac{a}{2}+ 1$ . Solve that equation for a.

Of course, that only works if the sequence converges. Here you can see that the first few numbers are 1, 3/2, 7/4, .... You should be able to prove, by induction, that this sequence is increasing and has 2 as an upper bound. By the "monotone sequence theorem", then, the sequence converges.
January 25th 2010, 04:07 AM
chisigma

The sequence is defined by the recursive equation...

$a_{n}= 1+ \frac{a_{n-1}}{2}$ (1)

... and from (1) we derive that...

$\Delta_{n} = a_{n}-a_{n-1}= 2 - a_{n}$ (2)

The sequence admits finite limit if and only if $\lim_{n \rightarrow \infty} \Delta_{n}=0$ , so that from (2) we derive...

$\lim_{n \rightarrow \infty} a_{n}=2$ (3)

Kind regards

$\chi$ $\sigma$
January 25th 2010, 04:40 AM
PJani

HallsofIvy and chisigma:
thank you two

I know how to make induction on explicit sequences but i don't know how to make induction on recursive equations.
January 25th 2010, 04:55 AM
HallsofIvy

Recursive sequences, because they give an explicit formula for $x_{n+1}$ in terms of $x_n$ , are easier to use with induction!

For example, to prove this sequence is increasing:
1) If n= 1, $a_n= a_1= 1$ and $a_{n+1}= a_2= \frac{a_1}{2}+ 1= \frac{1}{2}+ 1= \frac{3}{2}$ so $a_2> a_1$ .

2) Assume that, for some k, $a_{k+1}> a_k$ . Then $a_{k+2}= \frac{a_{k+1}}{2}+ 1> \frac{a_k}{2}+ 1= x_{k+1}$ .
(I have used the fact that, since $a_{k+1}> a_k$ , $\frac{a_{k+1}}{2}> \frac{a_k}{2}$ .)

Its just as easy to prove that 2 is an upper bound for the sequence.