How to solve a recursively defined system

Question

It has been a while since I have tackled a problem like this and could use a refresher. I have a recursive system of equations that looks a little like:

$$x_{n}\left(\frac{1}{2}\right)+y_{n}\left(\frac{1}{4}\right)=x_{n+1} \\ x_{n}\left(\frac{1}{2}\right)+y_{n}\left(\frac{3}{4}\right)=y_{n+1}$$

Where the initial $x$ & $y$ values are given else where.

My question is how do I find the value of $x$ at $n=5$ iterations? Of course there is the naive method where you simply iterate through the $x$ and $y$ equations $5$ times. But something tells me there is a more efficient way to do this.

Answer 1

Probably the best answer uses linear algebra. You can rewrite this system as:

$$\begin{bmatrix} x_{n+1} \\ y_{n+1} \end{bmatrix} = \begin{bmatrix} \frac{1}{2} & \frac{1}{4} \\ \frac{1}{2} & \frac{3}{4} \end{bmatrix} \begin{bmatrix} x_n \\ y_n \end{bmatrix}.$$

This implies that

$$\begin{bmatrix} x_n \\ y_n \end{bmatrix} = A^n \begin{bmatrix} x_0 \\ y_0 \end{bmatrix}$$

where $A$ is the matrix above.

It is hard to exponentiate a general matrix but it is easy to exponentiate a diagonal matrix. This is why we diagonalize $A$ in this problem, which means we need the eigenvalues and eigenvectors. Here the characteristic polynomial is

$$p(\lambda)=\lambda^2-\frac{5}{4} \lambda + \frac{1}{4}.$$

You can find the roots $\lambda_1,\lambda_2$ of this polynomial with the quadratic formula. The eigenvectors $v_1,v_2$ are the solutions to $(A-\lambda I)v=0$ for each eigenvalue $\lambda$. Then the solution to your problem is given by

$$\begin{bmatrix} x_n \\ y_n \end{bmatrix} = c_1 \lambda_1^n v_1 + c_2 \lambda_2^n v_2$$

where $c_1,c_2$ are chosen such that $c_1 v_1 + c_2 v_2 = \begin{bmatrix} x_0 \\ y_0 \end{bmatrix}$. In an equivalent matrix form we have:

$$\begin{bmatrix} x_n \\ y_n \end{bmatrix} = \begin{bmatrix} v_1 & v_2 \end{bmatrix}\begin{bmatrix} \lambda_1^n & 0 \\ 0 & \lambda_2^n \end{bmatrix} \begin{bmatrix} v_1 & v_2 \end{bmatrix}^{-1} \begin{bmatrix} x_0 \\ y_0 \end{bmatrix}.$$

Here the calculations are actually fairly nice because you get $\lambda_1,\lambda_2 = \frac{\frac{5}{4} \pm \sqrt{\frac{25}{16} - 1}}{2} = \frac{\frac{5}{4} \pm \frac{3}{4}}{2} = \frac{5}{8} \pm \frac{3}{8}$.