# 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.

-
I made some edits, can you see if this is what you intended? –  Calvin Lin Apr 26 '13 at 3:52
Yes, it is. Thank you! –  Trixie Apr 26 '13 at 3:54
–  lab bhattacharjee Apr 26 '13 at 4:03

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.

-
Can you help with the diagonalization too? I've been struggling with that as well. –  Trixie Apr 26 '13 at 4:11

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.

-

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.

-