Convert a recursive sequence formula to explicit I need to convert the following formula
$$
a_{n+1} = 5a_n - 6a_{n - 1}
$$
into an explicit formula, so I can just put whatever $n$ and get the $n$-th element of the sequence.
I know how to extract the formula if I have 2 equations, for example:
$$
a_n = 2a_{n-1} + b_{n-1}\\
b_n = a_{n - 1} + 2b_{n-1}
$$
A matrix is needed ->
$$
A = 
\begin{bmatrix}
2 & 1 \\1 & 2
\end{bmatrix}\\
X = 
\begin{bmatrix}
a_{n-1}\\
b_{n-1}
\end{bmatrix}
$$
And then just calculate the eigenvalues and eigenvectors of the matrix and create a diagonal matrix($\Lambda$) and the eigenvector matrix ($P$) with them and get to the equation:
$$
AX = P\Lambda^{n-1} P^{-1}X
$$
And simply multiply everything to get the result in explicit form.
Is there a similar way to calculate explicit form of the equation above?
EDIT: $a_0 = a_1 = 1$
 A: Use generating functions. Rewrite the recurrence relation as
$$
a_{n + 2} = 5 a_{n + 1} - 6 a_n.
$$
Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the relation by $z^n$, and sum over $n \ge 0$ with the initial values to get
$$
\frac{A(z) - a_0 - a_1 z}{z^2} = 5 \frac{A(z) - a_0}{z} - 6 A(z).
$$
Solve for $A(z)$ and express the result as partial fractions, so we can
$$
A(z) = \frac{a_1 - 2 a_0}{1 - 3 z} - \frac{a_1 - 3 a_0}{1 - 2 z}.
$$
We can interpret these as just geometric series in closed form, so rewriting this gives us
$$
a_n = (a_1 - 2 a_0) \cdot 3^n - (a_1 - 3 a_0) \cdot 2^n.
$$
The same technique (with minor modifications) works for a wide variety of recurrence relations.
A: The trick is to write down the matrix 
$$
A = \begin{bmatrix}
5 &-6\\
1 & 0\\
\end{bmatrix},
$$
so that
$$
\begin{bmatrix}
a_{n+1}\\
a_{n}
\end{bmatrix}
=
A
\begin{bmatrix}
a_{n}\\
a_{n-1}
\end{bmatrix}.
$$
Then proceed with the eigenvalues/eigenvectors analysis as you are used to.
A: A simple way to solve most difference equations is the following. Consider $a_{n+2} = 5 a_{n+1} - 6 a_{n}$ having solutions of the form $a_{n} = r^{n}$. From this it is seen that $r$ satisfies the quadratic equation $r^{2} - 5 r + 6 = 0$ for which the solutions are $r = 2, 3$. Hence $a_{n} = A \ 2^{n} + B \ 3^{n}$, where $A$ and $B$ are to be determined from the initial conditions. 
A: There are easier ways to do this, but if $x^2=5x-6$ then $(x-2)(x-3)=0$
Now set $b_n=a_n-2a_{n-1}; c_n=a_n-3a_{n-1}$
Then $b_{n+1}=3b_n [+0c_n]$ and $c_{n+1}=[0b_n + ]2c_n$ are in the form you wanted, and your matrix is already diagonal.
Once you have solved this note that $a_{n-1}=b_n-c_n$
Easiest is to note that the roots - here $2$ and $3$ - of the auxiliary equation are the eigenvalues of the matrix, and the answer will therefore be of the form $A\cdot 2^n+B\cdot 3^n$ with $A, B$ determined by some other conditions on the system.
A: Hint: find a constant $c$ such that $a_{n+1} + ca_n$ is a geometric progression
