deriving the formula for linear recursions

azi · **Joined:** Fri, 21 Sep 2007 17:15:28 UTC **Posts:** 47

Hello!

I know there is a formula related to recursions of the type

$x_{n+2} = ax_{n+1} + bx_{n}$ where x_0,x_1,a,b

are known. I'm now interested in deriving this formula using the propriety

$\begin{bmatrix} x_{n+2} \\ x_{n+1} \\ \end{bmatrix} = \begin{bmatrix} a & b \\ 1 & 0 \\ \end{bmatrix} * \begin{bmatrix} x_{n+1} \\ x_{n} \\ \end{bmatrix}$

So if we denote $A := \begin{bmatrix} a & b \\ 1 & 0 \\ \end{bmatrix}$

then it follows that
$\begin{bmatrix} x_{n+2} \\ x_{n+1} \\ \end{bmatrix} = A^{n-1} * \begin{bmatrix} x_{1} \\ x_{0} \\ \end{bmatrix}$

If we assume

is diagonizable then we can write

$\begin{bmatrix} x_{n+2} \\ x_{n+1} \\ \end{bmatrix} = \begin{bmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \\ \end{bmatrix} * \begin{bmatrix} \lambda_{1}^{n-1} & 0 \\ 0 & \lambda_{2}^{n-1} \\ \end{bmatrix} * \begin{bmatrix} 1 & -\lambda_2 \\ -1 & \lambda_1 \\ \end{bmatrix} * \begin{bmatrix} \frac{x_1}{\lambda_1 - \lambda_2} \\ \frac{x_2}{\lambda_1 - \lambda_2} \\ \end{bmatrix}$

After I multiply to obtain the equality for $x_{n+2}$ I get some ugly multiplications, so I'm wondering what did I do wrong or, eventually, how to simplify the obtained equation to get the correct formula for linear recursions.

Thanks

tashirosgt · **Posted:** Wed, 18 Feb 2009 06:19:54 UTC

You should tell us what "this formula" is.

Suppose we take the matrix approach.If

is diagonal and
$D = P^{-1}\ A\ P$

Then

$D^n = ( P^{-1} A P)(P^{-1} A P) ....(P^{-1} A P) = P^{-1} A^n P$

$A^n = P \ D^n \ P^{-1}$

$\begin {pmatrix} x_{n+1} \\ x_n \end {pmatrix} = A^n \begin {pmatrix} x_0 \\ x_1 \end {pmatrix} = P \ D^n P^{-1} \begin {pmatrix} x_0 \\ x_1 \end {pmatrix}$

Since the last expression is easy to compute, some people would call that "the formula" for the solution.

On the other hand, there is an approach to solving the equation based on the "lag operator", as given in the pdf file:
http://www.google.com/url?sa=U&start=1& ... 9kXSRXDERg

It would interesting to understand how these two approaches are related.

S.O.S. Mathematics CyberBoard

deriving the formula for linear recursions

Who is online