### cpcesar's blog

By cpcesar, history, 5 weeks ago, , Hi,
I'm solving problem K of this contest:
http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf
and I know it can be solved with fast matrix exponentiation.

I got to the step where I have the following two recurrences:

$f(1) = 1$
$f(2) = 6$
$f(n) = 2^{n-1}+2f(n-1)+4f(n-2) \qquad \forall n > 2$

$g(3) = 4$
$g(n) = 4f(n-2)+2g(n-1) \qquad \forall n > 3$

The result for input $n$ is $4f(n) + 2g(n)$, when n > 2.
But I have no idea how to find matrices to compute such recurrences.

Could someone please suggest me a good reference from where I can learn to find the correct matrices when solving matrix exponentiation problems? Comments (4)
 » 5 weeks ago, # | ← Rev. 6 →   UPD. Maybe you already know, but while $n \le 10^9$ you can solve it in $O(n)$.You need to introduce new function $h(n)$ in form $h(n)=f(n)-C \cdot 2^n$ and find such $C$ that after substitution into recurrence for $f(n)$ the term with $2^n$ will be equal to zero. After it you will have next recurrences:$h(n)=2\cdot h(n-1) + 4 \cdot h(n-2)$ and $g(n)=4 \cdot \left(h(n-2)+C \cdot 2^{n-2}\right) + 2 \cdot g(n-1)$After it you can apply this trick for recurrence for $g(n)$ too: introduce new function $r(n)$ that $r(n)=g(n)-C_1 \cdot 2^n$ and after finding $C_1$ you will have next recurrences:$h(n)=2 \cdot h(n-1)+4 \cdot h(n-2)$ and $r(n)=4 \cdot h(n-2)+2 \cdot r(n-1)$. Now you can solve it with matrix exponentiation: $\begin{bmatrix} h_1(k+1)\\ r(k+1)\\ h_0(k+1) \end{bmatrix} = \begin{bmatrix} 2 & 0 & 4\\ 0 & 2 & 4\\ 1 & 0 & 0 \end{bmatrix} \cdot \begin{bmatrix} h_1(k)\\ r(k)\\ h_0(k) \end{bmatrix}$UPD 2. A much easier way: introduce third function $h(n) = 2^{n-1}$. So, you will have linear recurrences for $h(n)$, $f(n)$ and $g(n)$.
•  » » Thanks for your explanation. I have found $C = -\frac{1}{2}$, but I got stuck on the step where I introduce $r(n) = g(n) - C_1 \cdot 2^{n}$ and try to find $C_1$.$r(n) = g(n) - C_1 \cdot 2^{n} \implies g(n) = r(n) + C_1 \cdot 2^{n}$ 1) $g(n) = -2^{n-1} + 4 \cdot h(n-2) + 2 \cdot g(n-1)$ 2) $r(n) = -2^{n-1} + 4 \cdot h(n-2) + 2 \cdot [r(n-1) + C_1 \cdot 2^{n-1}] - C_1 \cdot 2^{n}$ 3) $r(n) = -2^{n-1} + 4 \cdot h(n-2) + 2 \cdot r(n-1) + C_1 \cdot 2^{n} - C_1 \cdot 2^{n}$ 4) $r(n) = -2^{n-1} + 4 \cdot h(n-2) + 2 \cdot r(n-1)$$C_1$ got cancelled in line 3 so I cant find it. Another thing I would like to question if you don't mind: This trick seems to be applied to get a linear recurrence from another one that is not linear. Can matrix exponentiation be applied only to linear recurrences?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   Looks like it's not working with $C_1$. The only one way is introduce new function $h(n) = 2^{n}$, $h(n)=2h(n-1)$, $h(1)=2$ and add it to system. You can read about it in the link from another comment below.This trick can help only in transforming linear reccurence into homogeneous linear recurrence.
 »