Solving a system of recurrence relations

Question

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$

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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$

Answer 5

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.