# 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$

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.

• ok, so I got to the point where I get this vector: $\begin{bmatrix}3\cdot3^{n-1}+ 6\cdot2^{n-1}\\3^{n-1}+ 3\cdot2^{n-1} \end{bmatrix}$ but I am not sure whether it is correct – Mark May 26 '14 at 17:00

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.

• wow, this sure is a shortcut! But how do I determine A and B? As I followed @Andreas Caranti's answer I got to $\begin{bmatrix}3\cdot3^{n-1}+ 6\cdot2^{n-1}\\3^{n-1}+ 3\cdot2^{n-1} \end{bmatrix}$, but I don't think this is the answer. Any hint how do I proceed? – Mark May 26 '14 at 17:07
• @Mark - $A$ and $B$ are arbitrary - but if you were to know $a_0=p, a_1=q$ you'd solve $A+B=p; 2A+3B=q$ and skip the matrices- or you could plug $b_1=q-2p, c_1=q-3p$ into your matrix method. – Mark Bennet May 26 '14 at 17:11
• I forgot the initial values, they are $a_0 = a_1 = 1$, sorry but I did not quite get what I need to do with $b_1=q−2p,c_1=q−3p$ – Mark May 26 '14 at 17:19
• @Mark You should then get $B=-1, A=2$. I assumed that you had a way of plugging initial values into your matrix method - here $b_1=-1, c_1=-2$ – Mark Bennet May 26 '14 at 17:25
• and one more thing, how do we know that $b_n=a_n-2a_{n-1}; c_n=a_n-3a_{n-1}$ should actually be defined like this? – Mark May 26 '14 at 17:44

Use generating functions. Rewrite as: $$a_{n + 2} = 5 a_{n + 1} - 6 a_n$$ Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the recurrence by $z^n$ and sum over $n \ge 0$, with the initial values you have: $$\frac{A(z) a_0 - a_1 z}{z^2} = 5 \frac{A(z) - a_0}{z} - 6 A(z)$$ Solve for $A(z)$, express as partial fractions: $$A(z) = \frac{a_1 - 2 a_0}{1 - 3 z} - \frac{a_1 - 3 a_0}{1 - 2 z}$$ As those are just geometric series: $$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 recurrences.

Hint: find a constant $c$ such that $a_{n+1} + ca_n$ is a geometric progression

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.