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$
Best Answer
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.