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$
$\endgroup$ 25 Answers
$\begingroup$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.
$\endgroup$ $\begingroup$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.
$\endgroup$ 1 $\begingroup$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.
$\endgroup$ 7 $\begingroup$Hint: find a constant $c$ such that $a_{n+1} + ca_n$ is a geometric progression
$\endgroup$ $\begingroup$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.
$\endgroup$
