# Finding $a_n$ using a given matrix

I want to find a formula for $a_n$, where:

$a_0 = a,$
$a_1=b,$
$a_{n+2}=6a_{n+1}-9a_n$

By looking at $a_2, a_3, a_4$... I did manage to see some formula, but I don't think this is the right way.

Instead, in an earlier question, I'm asked to find the Jordan form of

$$A=\begin{pmatrix} 6 & -9 \\ 1 & 0 \end{pmatrix}$$

I found it to be

$$G=\begin{pmatrix} 3 & 1 \\ 0 & 3 \end{pmatrix}$$

Also, $G^n=3^{n-1}\begin{pmatrix} 3 & n \\ 0 & 3 \end{pmatrix}$

Now, I noticed that if $v=\begin{pmatrix} a_{n+1}\\ a_n \end{pmatrix}$, then $Av=\begin{pmatrix} 6a_{n+1}-9a_n\\ a_{n+1} \end{pmatrix}$ and for our sequence,

we need $$Av=\begin{pmatrix} 6a_{n+1}-9a_n\\ a_{n+1} \end{pmatrix}=\begin{pmatrix} a_{n+2}\\ a_{n+1} \end{pmatrix}$$

But from here on I'm not sure how to proceed.

-
We have $A^n\begin{pmatrix} a_1\\a_0\end{pmatrix} = \begin{pmatrix} a_{n+1}\\a_n\end{pmatrix}$, hence you only have to compute $A^n$. It won't be difficult since you have computed $G^n$. – Davide Giraudo Jun 23 '11 at 12:39

I don't think that there's much left to do for you. If you use the fact that $A = SGS^{-1}$, where

$$S = \begin{pmatrix}3&1\\1&0\end{pmatrix}$$

then you can simply calculate $$A^n v = (SGS^{-1})^n v = SG^nS^{-1}v$$ using the expression for $G^n$ that you obtained above and you should have your final result by reading off the entries of $A^n v$.

Regards, Jan

-
It's possible OP found the Jordan form without ever finding the matrix $S$. If so, that could be what OP was missing. – Gerry Myerson Jun 23 '11 at 13:01

What you are attempting to solve is a linear recurrence relation. Check out the book Concrete Mathematics. These are explicitly solvable.

-
Yes, but OP is trying to solve it by a particular method, namely, by building on the earlier problem. – Gerry Myerson Jun 23 '11 at 13:02