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$$$?

Timus — Fibonacci Sequence. The sequence $$$F$$$ satisfies the condition $$$F_n = F_{n-1} + F_{n-2}$$$. You're given $$$F_i$$$ and $$$F_j$$$, compute $$$F_n$$$.

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)$$$.

102129D - Basis Change. The sequence $$$F$$$ satisfies $$$F_n=\sum\limits_{i=1}^k a_i F_{n-i}$$$. Find $$$c_1,\dots,c_n$$$ such that $$$F_n = \sum\limits_{i=1}^k c_i F_{n-b_i}$$$.

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:

Matrices of this kind are called alternant matrices. Let's denote its determinant as $$$D_{\lambda_1, \dots, \lambda_k}(c_1, \dots, c_k)$$$, then the solution is

Unfortunately, on practice in makes more sense to find $$$\alpha_i$$$ with the Gaussian elimination rather than with these direct formulas.