<s>[INST] 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!
 [/INST] 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. $$
</s>