# Limits of recursive sequences

• Jan 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.
$\displaystyle a_1=1$
$\displaystyle a_{n+1}=\frac{a_n}{2}+1$

Is there any common way of solving all recursive limits?
• Jan 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.
$\displaystyle a_1=1$
$\displaystyle 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: $\displaystyle \lim a_{n+1}= \frac{\lim a_n}{2}+ 1$. If the limit exists and $\displaystyle \lim a_n= a$, then both of those limits are a. You get the equation $\displaystyle 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.
• Jan 25th 2010, 04:07 AM
chisigma
The sequence is defined by the recursive equation...

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

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

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

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

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

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$
• Jan 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.
• Jan 25th 2010, 04:55 AM
HallsofIvy
Recursive sequences, because they give an explicit formula for $\displaystyle x_{n+1}$ in terms of $\displaystyle x_n$, are easier to use with induction!

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

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

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