Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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

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.

share|cite|improve this answer
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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.