Building transformation matrix for solving recurrence relation of two series with matrix exponentiation

Question

Could you help to find a way to build a transformation matrix for the recurrence relation

$$ x_n = \begin{cases} x_{n-2} + y_{n-2} + y_{n-3}, & \mbox{if } n\ \geq 0 \\ 1 & \mbox{if } n \lt 0 \end{cases}\\ y_n = \begin{cases} y_{n-1} + x_{n-2} + y_{n-3}, & \mbox{if } n\ \geq 0 \\ 1 & \mbox{if } n \lt 0 \end{cases} $$

My first attempt was successful for simpler recurrence, but I didn't manage to find a generic approach:

$$ V_n = \begin{pmatrix} x_n \\ y_n \end{pmatrix} => V_{n+1}=\begin{pmatrix} x_{n+1} \\ y_{n+1} \end{pmatrix} = \begin{pmatrix} 5x_n - 3y_n \\ 4x_n - 2y_n \end{pmatrix} = \begin{bmatrix} 5 -3 \\ 4 -2 \end{bmatrix} \begin{pmatrix} x_n \\ y_n \end{pmatrix} \\ A = \begin{bmatrix} 5 -3 \\ 4 -2 \end{bmatrix} \\ V_0 = \begin{pmatrix} 2 \\ 1 \end{pmatrix} \\ V_n = A^nV_0 $$

Here is good explanation, but not for two series: http://www.math.cmu.edu/~mradclif/teaching/228F16/recurrences.pdf

Answer 1

This will be a little icky, but here you can represent this recurrence with the following $5 \times 5$ transformation matrix: $$M = \begin{bmatrix} 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{bmatrix}$$ Then all your equations (except the initial conditions) are expressed in the equation $$M \cdot \begin{bmatrix} x_{n - 1} \\ x_{n - 2} \\ y_{n - 1} \\ y_{n - 2} \\ y_{n - 3}\end{bmatrix} = \begin{bmatrix} x_n \\ x_{n - 1} \\ y_{n} \\ y_{n - 1} \\ y_{n - 2}\end{bmatrix}$$ You can then proceed to perform matrix exponentiation on $M$ and apply the matrix on the initial condition vector $$\vec{v}_0 = \begin{bmatrix} x_1 \\ x_0 \\ y_2 \\ y_1 \\ y_0\end{bmatrix}$$ the appropriate number of times to find the general form of $x_n$ and $y_n$.

EDIT: How exactly do you construct this matrix?

The motivation behind using matrices to solve linear recurrences is to find a matrix $M$ such that $\vec{v}_n = M \vec{v}_{n - 1}$, where $\vec{v}_n$ contains the recursion's quantities of interest (here we are interested in solving for $x_n$ and $y_n$, so we want $\vec{v}_n$ to contain both of them. Doing so effectively solves the recurrence, because it follows that $\vec{v}_n = M^{n - 1} \vec{v}_0$ (or something like that with $M$ raised to a slightly different power, depending on what the vector of initial conditions $\vec{v}_0$ is), which is something we can calculate directly.

In a first-degree recurrence (e.g. all terms with subscript $n$ depend only on terms with subscript $n - 1$), we can just choose $\vec{v}_n$ to be the vector $\begin{bmatrix} x_n \\ y_n \end{bmatrix}$ and we can treat the recurrence conditions as a matrix equation. For example, if the first-degree recurrence we seek to solve is $$\begin{cases} x_n = a x_{n-1} + b y_{n - 1} \\ y_n = c x_{n - 1} + d y_{n - 1} \end{cases}$$ then the corresponding matrix equation is $$\begin{bmatrix} a & b \\ c & d \end{bmatrix} \begin{bmatrix} x_{n-1} \\ y_{n-1} \end{bmatrix} = \begin{bmatrix} x_n \\ y_n \end{bmatrix}$$ Here you have a recurrence which is second-degree in $x_n$ and third-degree in $y_n$ (i.e. $x_n$ and $y_n$ depend on terms up till $x_{n - 2}$ and $y_{n -3}$), so our $\vec{v}_{n - 1}$ vector should include both $x_{n - 1}$ to $x_{n - 2}$ and should also include all terms from $y_{n - 1}$ to $y_{n - 3}$. So this mean $\vec{v}_n$ will contain both $x_n$ and $x_{n - 1}$, and $y_n$ thru $y_{n - 2}$.

To find the matrix, we just must find the matrix $M$ so that $$M \vec{v}_{n - 1} = M \begin{bmatrix} x_{n - 1} \\ x_{n - 2} \\ y_{n - 1} \\ y_{n - 2} \\ y_{n - 3} \end{bmatrix} = \vec{v}_n = \begin{bmatrix} x_n \\ x_{n - 1} \\ y_{n} \\ y_{n - 1} \\ y_{n - 2}\end{bmatrix}$$ The second, fourth, and fifth row will be easy to fill out (because $x_{n - 1}, ~ y_{n - 1}, $ and $y_{n-2}$ are entries in both $\vec{v}_n$). The first and third row will be filled out according to the linear combination of the elements of $\vec{v}_{n-1}$ that determine them.

If you have even more sequences (e.g. if you added $z_n$), you just have to follow a similar procedure, by adding whichever terms $z_n$ depends on to the vector $\vec{v}_{n-1}$, and fill out the matrix $M$ accordingly.