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)$$$. Specifically,
Therefore, our equation above is, equivalent to the following:
Equating coefficients near $$$x^1$$$ and $$$x^0$$$, we get the following system:
Substituting $$$a \mapsto a^{-1}$$$ and $$$b \mapsto b^{-1}$$$, we get it a bit simplified:
The determinant of this system of equations is $$$(a-b)(a^pb^q - a^qb^p)$$$. Solving the system, we get the solution
Doing the back-substitute $$$a \mapsto a^{-1}$$$ and $$$b \mapsto b^{-1}$$$, we get a somewhat 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?