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$
 A: 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$. 
A: A much more simplistic approach, similar to linear equations. You have $$X_{n+1} = 4X_n + Y_n$$ $$Y_{n+1} = 3Y_n + X_n$$ From the second equation, extract $X_n=Y_{n+1}-3Y_n$ which also mean $X_{n+1}=Y_{n+2}-3Y_{n+1}$. Replace now in the first equation to get $$Y_{n+2}-7Y_{n+1}+11Y_n=0$$ which, using the traditional method, leads to $$Y_n=c_1 \left(\frac{1}{2} \left(7-\sqrt{5}\right)\right)^n+c_2 \left(\frac{1}{2}
   \left(7+\sqrt{5}\right)\right)^n$$ Now, reuse $X_n=Y_{n+1}-3Y_n$
A: Let 
$$v_n=\begin{pmatrix} X_{n}\\Y_n\end{pmatrix}.$$
Then the given system can be written as
$$v_{n+1}=Av_n, \text{ where } A=\begin{pmatrix}4&1\\1&3\end{pmatrix}.$$
On solving the system (iteratively) you will get
$$v_{n}=A^nv_0.$$
Here $v_0$ is the vector corresponding to the initial conditions that would be given.
To get the higher powers of a matrix, you may want to go with diagnolization.
I have laid out some steps that can be used in general so hopefully this helps.
A: Just use generating functions directly. Define $X(z) = \sum_{n \ge 0} x_n z^n$ and $Y(z) = \sum_{n \ge 0} y_n z^n$. Multiply your recurrences by $z^n$ and sum over $n \ge 0$ to get by recognizing the resulting sums:
\begin{align}
\frac{X(z) - x_0}{z}
  &= 4 X(z) + Y(z) \\
\frac{Y(z) - y_0}{z}
  &= X(z) + 3 Y(z)
\end{align}
Solve for $X(z)$ and $Y(z)$:
\begin{align}
X(z)
  &= \frac{x_0- (3 x_0 - y_0) z}{1 - 7 z + 11 z^2} \\
Y(z)
  &= \frac{y_0 + (x_0 - 4 y_0) z}{1 - 7 z + 11 z^2}
\end{align}
Next steps are to split into partial fractions (a neat mess of irrationals, forgive me if I don' go though with it here) and read off the coeffients from the resulting geometric series.
A: One way is to write down their generating functions (i.e. multiply both sides by $z^n$ and sum over $n$), to get a system of algebraic equations in $Y(z)$ and $X(z)$ (the generating functions of $X_n$ and $Y_n$), and solve that system of equations. 
An excellent tutorial on generating functions is Generatingfunctionology by H. Wilf. 
