How to find solutions for linear recurrences using eigenvalues Use eigenvalues to solve the system of linear recurrences
$$y_{n+1} = 2y_n + 10z_n\\
z_{n+1} = 2y_n + 3z_n$$
where $y_0 = 0$ and $z_0 = 1$.
I have absolutely no idea where to begin. I understand linear recurrences, but I'm struggling with eigenvalues.
 A: Let $M = \begin{pmatrix} 2 & 10 \\ 2 & 3 \\ \end{pmatrix} $. Then we have $\begin{pmatrix} y_{n+1} \\ z_{n+1} \end{pmatrix} = M \begin{pmatrix} y_n \\ z_n \end{pmatrix}$, which gives us 
$$ \begin{pmatrix} y_n \\ z_n \end{pmatrix} = M^n \begin{pmatrix} y_0 \\ z_0 \end{pmatrix} =  M^n \begin{pmatrix} 0 \\ 1 \end{pmatrix}.$$
Now, if you know how to diagonalize a matrix, that makes calculating $M^n$ very easy. I'd leave it here, unless you need help with the diagonalization.
A: Write the vector $X_n = (y_n,z_n)$ so that
$$ X_{n+1} = 
\begin{pmatrix}
2 & 10  \\ 
2 & 3
\end{pmatrix}
X_n = M X_n.
$$ 
Show that $M$ is diagonalizable so that $M = U D U^T$ (I leave it to you to compute) for some diagonal matrix $D$ and orthogonal matrix $U$.  Then 
$$ X_{n+1} = UDU^T X_{n} = UDU^T UDU^T X_{n-1}= UD^2U^T X_{n-1} = \dotsc = U D^{n+1}U^T X_0.$$
So the cool thing is that to compute 
$$ X_{n+1} = 
\begin{pmatrix}
y_{n+1} \\ z_{n+1}
\end{pmatrix}
$$
we only need to know $U, U^T, X_0$, and $D^{n+1}$ (i.e. just the eigenvalues), and we don't need to compute anything via recurrences.  We just compute directly via powers.
A: Set $x_n=[y_n z_n]^T$, and your system becomes $x_{n+1}=\left[\begin{smallmatrix}2&10\\2&3\end{smallmatrix}\right]x_n$.  Iteration becomes matrix exponentiation.  If your eigenvalues are less than 1 in absolute value, the matrix approaches 0.  If an eigenvalue is bigger than 1 in absolute value, you get divergence.  It's a rich subject, read about it on Wikipedia.
