2
$\begingroup$

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$
1
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Mark May 26 '14 at 17:00
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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Mark May 26 '14 at 17:07
  • $\begingroup$ @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. $\endgroup$ – Mark Bennet May 26 '14 at 17:11
  • $\begingroup$ 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$ $\endgroup$ – Mark May 26 '14 at 17:19
  • $\begingroup$ @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$ $\endgroup$ – Mark Bennet May 26 '14 at 17:25
  • $\begingroup$ 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? $\endgroup$ – Mark May 26 '14 at 17:44
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.