Linear algebra on Fibonacci number 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!
 A: One way (which was correctly indicated in an answer that has been, alas, deleted by owner) is to 


*

*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);

*find two (non-zero) geometric sequences $a_{n} = q^{n}$ that are a basis for this space;

*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.
A: 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. $$
