recurrence relation with offset techinique

general
1

A recurrence relation of this type: F_n = 2F_{n - 1} + 3F_{n - 2} + 3 , where sum of the coefficient of recurring terms on both side of the equation is not equal.

I have seen a codechef video ( by Kevin ) where they explain the offset adding to solve this type of recurrence by removal of the constant term. The recurrence can be converted to G_n = 2G_{n-1} + 3G_{n-2} and later use matrix exponentiation to solve it with matrix \begin{bmatrix} 2&3\\ 1&0\\ \end{bmatrix} to obtain the value of G_n \textit{ mod }M. For example,

\begin{aligned} &\text{Let, }F_n = G_n + C\\ &\Rightarrow G_n + C = 2\left [ G_{n - 1} + C \right ] + 3\left [ G_{n - 2} + C \right ] + 3 \\ &\Rightarrow G_n + C = 2G_{n - 1} + 3G_{n - 2} + 5C + 3 \\ &\Rightarrow G_n= 2G_{n - 1} + 3G_{n - 2} + 4C + 3 \\ &\Rightarrow C = -\frac{3}{4} \\ \end{aligned}

Now after calculating the value of G_n \textit{ mod }M how to recover F_n?

Thanks!

2

If you don’t know how to solve 4x \equiv 1 \pmod{M} , you can read about Extended Euclid Algorithm or Euler Theorem in Wikipedia. Or even find the solution using bruteforce approach.

3

Thank You, I understood modulo inverse, but in this case we have G_n -\frac{3}{4}. How to deal with this.
Is it equal to this ? (((4.G_n) \textit{ mod }M - 3 + M)\textit{ mod }M * 4^{-1})\textit{ mod }M

4

F_n = (G_n - 3 * 4^{-1}) \bmod{M}

5

Thank You !

6

How can you use F_n = G_n+C ? F_n and G_n doesn’t need to have a constant difference.