Converting recurrence relation to linear and solve with matrix exponentiation 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.
 A: 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.
