# recursive sequence

• January 14th 2009, 03:17 AM
omer.jack
recursive sequence
Hi

i have the recursive sequence which is defined this way:

A(1) = p
A(2) = q

A(n) = 0.5[A(n-1) + A(n-2)]

and i need to prove convergence and find the limit

it is very easy to prove convergence of the sequence from cantor's theorem

it is also possible to see that the limit is L=[p+2q]/3 but i cant manage to prove that this is the limit

• January 14th 2009, 06:17 AM
Jester
Quote:

Originally Posted by omer.jack
Hi

i have the recursive sequence which is defined this way:

A(1) = p
A(2) = q

A(n) = 0.5[A(n-1) + A(n-2)]

and i need to prove convergence and find the limit

it is very easy to prove convergence of the sequence from cantor's theorem

it is also possible to see that the limit is L=[p+2q]/3 but i cant manage to prove that this is the limit

If we assume the solution of the difference equation is of the form

$a_n = c \rho^n$

then substituting into

$2a_n - a_{n-1} - a_{n-2} = 0$

gives

$2 \rho^2 - \rho - 1 = 0$

which has two solutions: $\rho = 1,\;\; -\frac{1}{2}$

so the general solution of your difference equation is

$a_n = c_1 + c_2 \left( - \frac{1}{2} \right)^n$

Using the fact that $a_1 = p,\;\;\;a_2 = q$ gives $c_1 = \frac{1}{3}(p+3q)\;\;\;c_2 = - \frac{4}{3}(p-q)$ so

$a_n = \frac{1}{3}(p+3q) - \frac{4}{3}(p-q) \left( - \frac{1}{2} \right)^n$

Now as $n\, \rightarrow\, \infty$ the last term drops giving $a_n \rightarrow \frac{1}{3}(p+3q)$
• January 14th 2009, 07:04 AM
PaulRS
Okay, we have $2a_{n+2}=a_{n+1}+a_n$ thus: $2(a_{n+2}-a_{n+1})=a_n-a_{n+1}$

So define $b_n=a_{n+1}-a_{n}$ to get: $2b_{n+1}=-b_{n}$

And that can be easily solved. $b_{n}=\left(- \tfrac{1}{2}\right)\cdot{b_{n-1}}=...=\left(- \tfrac{1}{2}\right)^n\cdot{b_{0}}$

Now sum: $a_n-a_0=\sum_{k=0}^{n-1}{\left(a_{k+1}-a_k\right)}= \sum_{k=0}^{n-1}b_k=b_0 \cdot \sum_{k=0}^{n-1}\left(- \tfrac{1}{2}\right)^k$

And now this is just a geometric sum

In fact we have: $\lim_{n\to +\infty}a_n=a_0+b_0 \cdot \sum_{k=0}^{\infty}\left(- \tfrac{1}{2}\right)^k=a_0+b_0 \cdot\frac{1}{1+\tfrac{1}{2}}$
• January 14th 2009, 07:33 AM
omer.jack
thanks guys that was very helpful