# Thread: Recursive Sequence Convergence

1. ## Recursive Sequence Convergence

$x_0 > x_1$ and r and s are positive numbers with p + q = 1. $x_n = px_{n-1} + qx_{n-2}$ for all $n \geq 2$. Prove that $(x_n)$ is convergent and find limits in terms of $x_0, x_1$, p and q.

Okay I began by letting p = 1 - q so I could eliminate that variable. Then I began working it out up to $x_7$ but I couldn't find any pattern in terms of coefficients of the polynomial. It's a polynomial with respect to p. I am trying to get this to work out to something that I can put into summation notation, prove it is monotone, and then find an upper and/or lower bound but I am unsure how to go about putting it in summation notation - it's entirely possible this is not the way to do it but it seems most logical to me. The first term (in order of descending exponent on p) of the expansion is always $p^{n-1}*a_1$. The last term is $a_0$ when n is even and $a_1$ when n is odd. These are the only real patterns I've been able to discern though. Any insight is much appreciated. Thanks.

2. Here is an idea for you The sequence can be written as follows

$\begin{bmatrix}0 && 1 \\ (1-p) && p \end{bmatrix}\begin{bmatrix} x_{n-2} \\x_{n-1}\end{bmatrix}=\begin{bmatrix} x_{n-1} \\x_{n}\end{bmatrix}$

This matrix can be diagonalized and solved explicitly

For the two eigenvalues I got

$\lambda = p-1 \text{ or } \lambda =1$

I hope this helps.

3. Originally Posted by valerian
$x_0 > x_1$ and r and s are positive numbers with p + q = 1. $x_n = px_{n-1} + qx_{n-2}$ for all $n \geq 2$. Prove that $(x_n)$ is convergent and find limits in terms of $x_0, x_1$, p and q.

Okay I began by letting p = 1 - q so I could eliminate that variable. Then I began working it out up to $x_7$ but I couldn't find any pattern in terms of coefficients of the polynomial. It's a polynomial with respect to p. I am trying to get this to work out to something that I can put into summation notation, prove it is monotone, and then find an upper and/or lower bound but I am unsure how to go about putting it in summation notation - it's entirely possible this is not the way to do it but it seems most logical to me. The first term (in order of descending exponent on p) of the expansion is always $p^{n-1}*a_1$. The last term is $a_0$ when n is even and $a_1$ when n is odd. These are the only real patterns I've been able to discern though. Any insight is much appreciated. Thanks.
The sequence is defined by the 'recursive relation'...

$\displaystyle x_{n} - p\ x_{n-1} - q\ x_{n-2}=0$ (1)

... that is 'linear and homogeneous' and the solution of which is...

$\displaystyle x_{n} = c_{1}\ \alpha_{1}^{n} + c_{2}\ \alpha_{2}^{n}$ (2)

... where $c_{1}$ and $c_{2}$ are 'arbitrary constants' that depend from $x_{0}$ and $x_{1}$ , $\alpha_{1}$ and $\alpha_{2}$ the solution of the 'characteristic equation'...

$\displaystyle \alpha^{2}- p\ \alpha - q= 0 \implies \alpha= \frac{p \pm \sqrt{p^{2}+4\ p -4}}{2}$ (3)

Now for $0< p= 1-q <1$ is $|\alpha_{1}|<1$ and $|\alpha_{2}|<1$ , so that in any case is...

$\displaystyle \lim_{n \rightarrow \infty} x_{n} = 0$ (4)

Kind regards

$\chi$ $\sigma$

4. Put x_n=m^n... and try to solve the quadratic equation... (hmmm...)

[EDIT: 4 MINUTES LATE]