Converting recurrence relation to linear and solve with matrix exponentiation

Question

Let's say we have the recurrence relation $$ x_n = \begin{cases} x_{n-1} + y_{n-2} + y_{n-3} + n2^n, & \mbox{if } n\ \geq 0 \\ 1 & \mbox{if } n \lt 0 \end{cases}\\ y_n = \begin{cases} y_{n-2} + x_{n-1} + x_{n-1} + n4^n, & \mbox{if } n\ \geq 0 \\ 1 & \mbox{if } n \lt 0 \end{cases} $$

How to build a transformation matrix for the recurrence relation and solve it with matrix exponentiation?

If it would be possible to get rid of $n2^n$ and $n4^n$, then we can build the transformation matrix for the linear recurrence relation:

$$ T = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 2 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix} $$

And eventually, we will be able to use $\vec{V_n} = T^{n+1} \cdot \vec{V_{-1}}$ formula to find $x_n$ and $y_n$.

However, the recurrence is no longer linear with the additional parts. As I understand, it's possible to represent additional part other way: $d^{n+1} = d(d^n) => (n+1)d^{n+1} = d(nd^n) + d(d^n)$, but I don't know where to move further.

I would really appreciate it if you could help me to find a way to build a transformation matrix for this recurrence.

Answer 1

I think you can use this matrix for the transition $$ \begin{pmatrix} 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 2 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 4 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 4 & 0 & 4 \\ \end{pmatrix} $$

The bottom-right $4 \times 4$ block will take care of generating $2^n$, $4^n$, $n \, 2^n$, and $n \, 4^n$, with a starting vector of $(1, 1, 1, 1, 2, 4, 2, 4)^T$. The non-zero entries in the top-right $4 \times 4$ block add the terms $n \, 2^n$ and $n \, 4^n$ to each of the $x_n$, $y_n$. The top-left block is what you wrote in the question. It uses the fact that $(n+1) \, a^{n+1}$ can be written as a linear combination of $n a^n$ and $a^n$.

EDIT: In response to the question, some further details on the matrix and state vector.

The state vector needs have four elements to carry the previous sequence terms needed in the recurrence: $x_{n-1}, y_{n-1}, y_{n-2}, y_{n-3}$. For the above, these are the first four components of the vector.

The next two components of the state vector carry values for $2^n$ and $4^n$, these are generated by powers of the $2 \times 2$ sub-matrix in the first part of the lower-right quarter-block $$ \begin{pmatrix} 2 & 0 \\ 0 &4 \end{pmatrix} $$

It needs two further terms to carry the values of $n \, 2^n$ and $n \, 4^n$. These are the last two components of the state vector.

Note that $$ (n+1) 2^{n+1} = 2 \left( n \, 2^n \right) + 2 \left( 2^n \right) $$ i.e. $(n+1) 2^{n+1}$ is a linear combination of $n \, 2^n $ and $ 2^n $, with a similar comment for the $n \, 4^n$ term. The bottom two rows of the transition matrix represent these linear relationships.