Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
    
add comment

3 Answers

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|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
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.