Flaker's blog

By Flaker, history, 5 weeks ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it
Spoiler
  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it -10 Vote: I do not like it

    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
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      For the particular $$$n=5$$$ it gives incorrect result:

      Spoiler

      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.