Hi everyone!
Today I'd like to write about Fibonacci numbers. Ever heard of them? Fibonacci sequence is defined as $$$F_n = F_{n-1} + F_{n-2}$$$.
It got me interested, what would the recurrence be like if it looked like $$$F_n = \alpha F_{n-p} + \beta F_{n-q}$$$ for $$$p \neq q$$$?
Using $$$L(x^n) = F_n$$$ functional, we can say that we essentially need to solve the following system of equations:
To get the actual solution from it, we should first understand what exactly is the remainder of $$$x^n$$$ modulo $$$x^2-x-1$$$. The remainder of $$$P(x)$$$ modulo $$$(x-a)(x-b)$$$ is generally determined by $$$P(a)$$$ and $$$P(b)$$$:
Therefore, our equation above is, equivalent to the following:
The determinant of this system of equations is $$$a^{-p}b^{-q} - a^{-q}b^{-p}$$$. Solving the system, we get the solution
Multiplying numerators and denominators by $$$a^q b^q$$$ for $$$\alpha$$$ and $$$a^p b^p$$$ for $$$\beta$$$, we get a nicer form:
This is a solution for a second degree recurrence with the characteristic polynomial $$$(x-a)(x-b)$$$.
Note that for Fibonacci numbers in particular, due to Binet's formula, it holds that
Substituting it back into $$$\alpha$$$ and $$$\beta$$$, we get
which is a neat symmetric formula.
P. S. you can also derive it from Fibonacci matrix representation, but this way is much more fun, right?
UPD: I further simplified the explanation, should be much easier to follow it now.
Note that the generic solution only covers the case of $$$(x-a)(x-b)$$$ when $$$a \neq b$$$. When the characteristic polynomial is $$$(x-a)^2$$$, the remainder of $$$P(x)$$$ modulo $$$(x-a)^2$$$ is determined by $$$P(a)$$$ and $$$P'(a)$$$:
Therefore, we have a system of equations
For this system, the determinant is $$$\frac{q-p}{a^{p+q+1}}$$$ and the solution is
Another interesting way to get this solution is via L'Hôpital's rule:
Let's consider the more generic case of the characteristic polynomial $$$(x-\lambda_1)(x-\lambda_2)\dots (x-\lambda_k)$$$.
We need to find $$$\alpha_1, \dots, \alpha_k$$$ such that $$$F_n = \alpha_1 F_{n-c_1} + \dots + \alpha_k F_{n-c_k}$$$. It boils down to the system of equations
This system of equations has a following matrix:
Let's denote its determinant as $$$D_{\lambda_1, \dots, \lambda_k}(c_1, \dots, c_k)$$$, then the solution is given as
Unfortunately, on practice in makes more sense to find $$$\alpha_i$$$ with the Gaussian elimination rather than with these direct formulas. If you'd like to practice the competitive programming version of this problem, you should try 102129D - Basis Change :).