1. ## 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

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

$\displaystyle a_n = c \rho^n$

then substituting into

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

gives

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

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

so the general solution of your difference equation is

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

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

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

Now as $\displaystyle n\, \rightarrow\, \infty$ the last term drops giving $\displaystyle a_n \rightarrow \frac{1}{3}(p+3q)$

3. Okay, we have $\displaystyle 2a_{n+2}=a_{n+1}+a_n$ thus: $\displaystyle 2(a_{n+2}-a_{n+1})=a_n-a_{n+1}$

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

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

Now sum: $\displaystyle 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: $\displaystyle \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}}$

4. thanks guys that was very helpful