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?