Solving a system of recurrence relations What is the methodology to solve for a system of recurrence relations?
For example:
$X_{n+1} = 4X_n + Y_n$
$Y_{n+1} = 3Y_n + X_n$

First, write it in matrix form: 
$\begin{bmatrix}x_{n+1} \\ y_{n+1}\end{bmatrix} = \begin{bmatrix}4&1 \\ 1&3\end{bmatrix}\begin{bmatrix}x_{n} \\ y_{n}\end{bmatrix}$. 
Let $z_n = \begin{bmatrix}x_{n} \\ y_{n}\end{bmatrix}$ and $A = \begin{bmatrix}4&1 \\ 1&3\end{bmatrix}$. Then, $z_{n+1} = Az_n$. 
Hence, the solution is $z_n = A^nz_0$. 
To make computing $A^n$ easier, diagonalize it as $A = VDV^{-1}$ where $D$ is a diagonal matrix with the eigenvalues of $A$ and $V$ is a matrix whose columns are the eigenvectors of $A$. 
Then, $A^n = VD^nV^{-1}$. The matrix $D^n$ is also a diagonal matrix, whose entries are just the $n$-th powers of the eigenvalues of $A$. This makes computing $A = VD^nV^{-1}$ easier than multiplying $A^n = A \cdots A$. 
