When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Flaker's blog

By Flaker, history, 4 years 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

| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Spoiler