### Flaker's blog

By Flaker, history, 5 weeks ago, ,

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.

• +7

 » 5 weeks ago, # |   +3 SpoilerFor your example, let the vector be $\overrightarrow{V_n} \equiv \begin{pmatrix} x_n \\ n 2^n \\ 2^n \\ y_n \\ y_{n - 1} \\ y_{n - 2} \\ n 4^n \\ 4^n \end{pmatrix}.$Each value in $\overrightarrow{V_{n+1}}$ is a linear combination of the values in $\overrightarrow{V_n}$.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   -10 Thank you for your reply tugsuu!I've tried to do it this way, but the result of $T^{n+1} \cdot \vec{V_{-1}}$ was incorrect: Spoiler$\begin{cases} x_n = x_{n-1} + y_{n-2} + y_{n-3} + n2^n \\ y_n = y_{n-2} + x_{n-1} + x_{n-1} + n4^n \end{cases} => \begin{cases} x_{n+1} = x_{n} + y_{n-1} + y_{n-2} + 2n2^n + 2 \cdot 2^n \\ y_{n+1} = y_{n-1} + 2x_{n} + 4n4^n + 4 \cdot 4^n \end{cases}=>\\$ $\vec{V_n} = \begin{pmatrix} x_n \\ n2^n \\ 2^n \\ y_n \\ y_{n-1} \\ y_{n-2} \\ n4^n \\ 4^n \end{pmatrix} => \vec{V_{n+1}} = \begin{pmatrix} x_{n} + y_{n-1} + y_{n-2} + 2n2^n + 2 \cdot 2^n \\ n2^n \\ 2^n \\ y_{n-1} + 2x_{n} + 4n4^n + 4 \\ y_{n-1} \\ y_{n-2} \\ n4^n \\ 4^n \end{pmatrix} =>$ $T = \begin{bmatrix} 1 & 2 & 2 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 1 & 0 & 4 & 4 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix}; \vec{V_{-1}} = \begin{pmatrix} 1 \\ -0.5 \\ 0.5 \\ 1 \\ 1 \\ 1 \\ -0.25 \\ 0.25 \end{pmatrix}$
•  » » » 4 weeks ago, # ^ |   0 In addition, I've made an attempt to use $\vec{V_{0}}$ instead of $\vec{V_{-1}}$, however the result is also incorrect with my calculations: Spoiler$\vec{V_{0}} = \begin{pmatrix} 3 \\ 0 \\ 1 \\ 3 \\ 1 \\ 1 \\ 0 \\ 1 \end{pmatrix} => \vec{V_n} = T^{n} \cdot \vec{V_{0}} = \begin{bmatrix} 1 & 2 & 2 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 1 & 0 & 4 & 4 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix}^n \cdot \begin{pmatrix} 3 \\ 0 \\ 1 \\ 3 \\ 1 \\ 1 \\ 0 \\ 1 \end{pmatrix}$For the particular $n=5$ it gives incorrect result: Spoiler$\vec{V_n} = \begin{bmatrix} 1 & 2 & 2 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 1 & 0 & 4 & 4 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix}^5 \cdot \begin{pmatrix} 3 \\ 0 \\ 1 \\ 3 \\ 1 \\ 1 \\ 0 \\ 1 \end{pmatrix} = \\ \begin{bmatrix} 1 & 10 & 10 & 0 & 5 & 5 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 16 & 16 & 0 & 9 & 8 & 4 & 4 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} \cdot \begin{pmatrix} 3 \\ 0 \\ 1 \\ 3 \\ 1 \\ 1 \\ 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 23 \\ 0 \\ 1 \\ 43 \\ 1 \\ 1 \\ 0 \\ 1 \end{pmatrix}$Thus, actual result is $x_5=23$ and $y_5=43$ which is incorrect, expected result is $x_5 = 631$ and $y_5=5723$.I would really appreciate it if you could point out my mistake.P.S. Sorry for posting the previous reply without spoilers.