5

Consider the sequence $\{a_n\}_{n\ge 0}$ given by the recurrence relation $$a_0=1,\ a_1=-1,\ a_{n+1}=3a_n+10a_{n-1}\ \ \text{for } n\ge2$$ And I am asked to work out the closed form expression for an in the same fashion as the proof for Fibonacci numbers by using linear algebra way

Thanks all for the help!

Chloe
  • 83
  • 1
    Have you found the $2\times 2$ matrix $A$ such that $\pmatrix{a_n\a_{n+1}}=A,\pmatrix{a_{n-1}\a_n}$? – Berci Apr 15 '13 at 08:02
  • Is it (a1,a2)=A(a0,a1) so (-1,7)=A(1,-1),then I am not sure how to do next, please guide me along, I am weak in this topic. – Chloe Apr 15 '13 at 08:12
  • I think what you want to do is show us the proof you refer to for the Fibonaccis, and we can help you adapt that proof to the recurrence at hand. – Gerry Myerson Apr 15 '13 at 12:48

2 Answers2

7

One way (which was correctly indicated in an answer that has been, alas, deleted by owner) is to

  1. note that the sequences satisfying $a_{n+1}=3a_n+10a_{n-1}$ form a two-dimensional space ($a_0$ and $a_1$ being the free parameters);
  2. find two (non-zero) geometric sequences $a_{n} = q^{n}$ that are a basis for this space;
  3. express the given sequence $a_{n}$ as a linear combination of the two geometric sequences $q_1^{n}$ and $q_2^{n}$ found in the previous step.

The ratio $q$ for the geometric sequences in step 2 can be found by solving $q^{n+1} = 3 q^{n} + 10 q^{n-1}$, or $$ q^{2} - 3 q - 10 = 0. $$ In step 3, one needs to find constants $c, d$ such that $a_{0} = c + d$ and $a_{1} = c q_{1} + d q_{2}$.

Equivalently, as suggested by Berci in a comment, note that $$ \begin{bmatrix}a_{n+1}\\a_{n}\end{bmatrix} = \begin{bmatrix}3 & 10\\1&0\end{bmatrix} \begin{bmatrix}a_{n}\\a_{n-1}\end{bmatrix}, $$ find the eigenvalues of the matrix (which are, unsurprisingly, the $q$ above) and conjugate the matrix to diagonal form.

See a good general explanation.

Andreas Caranti
  • 68,873
2

We can use the generating function $f(x)$ of $\{a_n\}$ to solve. Let $f(x)=\sum_{n=0}^\infty a_nx^n$. Then \begin{eqnarray*} f(x)&=&\sum_{n=0}^\infty a_nx^n=1-x+\sum_{n=2}^\infty a_nx^n\\ &=&1-x+\sum_{n=1}^\infty a_{n+1}x^{n+1}\\ &=&1-x+\sum_{n=1}^\infty (3a_{n}+10a_{n-1})x^{n+1}\\ &=&1-x+3\sum_{n=1}^\infty a_{n}x^{n+1}+10\sum_{n=1}^\infty a_{n-1}x^{n+1}\\ &=&1-x+3x\sum_{n=1}^\infty a_{n}x^{n}+10x^2\sum_{n=1}^\infty a_{n-1}x^{n-1}\\ &=&1-x+3x(f(x)-1)+10x^2f(x) \end{eqnarray*} from which we obtain the following function equation $$ f(x)=1-x+3x(f(x)-1)+10x^2f(x). $$ Hence \begin{eqnarray*} f(x)&=&\frac{4x-1}{10x^2+3x-1}\\ &=&\frac{6}{7}\frac{1}{1+2x}+\frac{1}{7}\frac{1}{1-5x}\\ &=&\frac{6}{7}\sum_{n=0}^\infty (-2)^nx^n+\frac{1}{7}\sum_{n=0}^\infty 5^nx^n \end{eqnarray*} and so $$ a_n=\frac{6}{7}(-2)^n+\frac{1}{7}5^n. $$

xpaul
  • 44,000