Way to solve recurrence relation with exponentiation of transformation matrix

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Hello everyone!

I'm trying to find a way to solve a recurrence relation using matrix exponentiation for the problem. The main goal is to be able to solve a recurrence relation for arbitrary $$$a, b, c, d, e, f, g, h$$$

$$$ x_n = \begin{cases} x_{n-a} + y_{n-b} + y_{n-c} + n \cdot d^n, & \mbox{if } n\ \geq 0 \\ 1 & \mbox{if } n \lt 0 \end{cases}\\ y_n = \begin{cases} y_{n-e} + x_{n-f} + x_{n-g} + n \cdot h^n, & \mbox{if } n\ \geq 0 \\ 1 & \mbox{if } n \lt 0 \end{cases} $$$

I've tried to find a solution on paper for the particular 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} $$$

I've started from building the transformation matrix for simpler homogenous recurrence relation. So, if we just drop $$$n \cdot d^n$$$ and $$$n \cdot h^n$$$ for some time, then transformation matrix for that relation takes the form:

$$$

\begin{cases} x_n = x_{n-1} + y_{n-2} + y_{n-3}\\ y_n = y_{n-2} + 2x_{n-1} \end{cases} => \vec{V_{n}} = \begin{pmatrix} x_{n} \\ y_{n} \\ y_{n-1} \\ y_{n-2} \end{pmatrix} => \vec{V_{n+1}} = \begin{pmatrix} x_{n+1} \\ y_{n+1} \\ y_{n} \\ y_{n-1} \end{pmatrix} = \begin{pmatrix} x_{n}+y_{n-1}+y_{n-2} \\ y_{n-1} + 2x_n \\ y_{n} \\ y_{n-1} \end{pmatrix} =>\\ 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 ($$$n \cdot d^n$$$ and $$$n \cdot h^n$$$). My first idea was to add $$$n2^n$$$ and $$$n4^n$$$ to the vector and it doesn't work:

$$$ \vec{V_{n}} = \begin{pmatrix} x_{n} \\ n2^n \\ y_{n} \\ y_{n-1} \\ y_{n-2} \\ n4^n \end{pmatrix} $$$

As I understand we are working with the non-homogeneous non-linear recurrence relation and we need to convert it to linear somehow. I would really appreciate it if you could help me to understand how to build a transformation matrix for the original recurrence relation from the problem.

Блог пользователя Flaker