Basis change in linear recurrences

Basis change in linear recurrences

Hi everyone!

Today I'd like to write about Fibonacci numbers. Ever heard of them? Fibonacci sequence is defined as .

It got me interested, what would the recurrence be like if it looked like for ?

Timus — Fibonacci Sequence. The sequence satisfies the condition . You're given and , compute .

Using 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 modulo . The remainder of modulo is generally determined by and :

Therefore, our equation above is, equivalent to the following:

The determinant of this system of equations is . Solving the system, we get the solution

Multiplying numerators and denominators by for and for , we get a nicer form:

This is a solution for a second degree recurrence with the characteristic polynomial .

Note that for Fibonacci numbers in particular, due to Binet's formula, it holds that

Substituting it back into and , 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 when . When the characteristic polynomial is , the remainder of modulo is determined by and :

Therefore, we have a system of equations

For this system, the determinant is 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 .

102129D - Basis Change. The sequence satisfies . Find such that .

We need to find such that . 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 , then the solution is

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