Basis change in Fibonacci numbers

Revision en5, by adamant, 2022-04-03 17:52:40

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:

$$$1 \equiv \alpha x^{-p} + \beta x^{-q} \pmod{x^2-x-1}.$$$

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

$$$ P(x) \equiv r \mod(x-a)(x-b) \iff \begin{cases}P(a) = r,\\ P(b)=r.\end{cases} $$$

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

$$$ \begin{cases} \alpha a^{-p} + \beta a^{-q} = 1,\\ \alpha b^{-p} + \beta b^{-q} = 1. \end{cases} $$$

The determinant of this system of equations is $$$a^{-p}b^{-q} - a^{-q}b^{-p}$$$. Solving the system, we get the solution

$$$ \begin{matrix} \alpha = \dfrac{b^{-q}-a^{-q}}{a^{-p}b^{-q} - a^{-q}b^{-p}}, & \beta = \dfrac{a^{-p}-b^{-p}}{a^{-p}b^{-q} - a^{-q}b^{-p}}. \end{matrix} $$$

Multiplying numerators and denominators by $$$a^q b^q$$$ for $$$\alpha$$$ and $$$a^p b^p$$$ for $$$\beta$$$, we get a nicer form:

$$$ \boxed{\begin{matrix} \alpha = \dfrac{a^q-b^q}{a^{q-p} - b^{q-p}}, & \beta = \dfrac{a^p-b^p}{a^{p-q} - b^{p-q}}. \end{matrix}} $$$

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

$$$F_n = \frac{a^n-b^n}{a-b}.$$$

Substituting it back into $$$\alpha$$$ and $$$\beta$$$, we get

$$$ \boxed{F_n = \frac{F_q}{F_{q-p}} F_{n-p} + \frac{F_p}{F_{p-q}} F_{n-q}} $$$

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

$$$ P(x) \equiv r \mod{(x-a)^2} \iff \begin{cases}P(a)=r,\\P'(a)=0.\end{cases} $$$

Therefore, we have a system of equations

$$$ \begin{cases} \alpha a^{-p} &+& \beta a^{-q} &=& 1,\\ \alpha p a^{-p-1} &+& \beta q a^{-q-1} &=& 0. \end{cases} $$$

For this system, the determinant is $$$\frac{q-p}{a^{p+q+1}}$$$ and the solution is

$$$ \boxed{\begin{matrix} \alpha = \dfrac{qa^p}{q-p},&\beta = \dfrac{pa^q}{p-q} \end{matrix}} $$$

Another interesting way to get this solution is via L'Hôpital's rule:

$$$ \lim\limits_{x \to 0}\frac{a^q-(a+x)^q}{a^{q-b}-(a+x)^{q-p}} = \lim\limits_{x \to 0}\frac{q(a+x)^{q-1}}{(q-p)(a+x)^{q-p-1}} = \frac{qa^p}{q-p}. $$$

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

$$$ \begin{cases} \alpha_1 \lambda_1^{-c_1}+\dots+\alpha_k \lambda_k^{-c_1} = 1,\\ \alpha_1 \lambda_1^{-c_2}+\dots+\alpha_k \lambda_k^{-c_2} = 1,\\ \dots\\ \alpha_1 \lambda_1^{-c_k}+\dots+\alpha_k \lambda_k^{-c_k} = 1.\\ \end{cases} $$$

This system of equations has a following matrix:

$$$ A=\begin{bmatrix} \lambda_1^{-c_1} & \lambda_2^{-c_1} & \dots & \lambda_k^{-c_1} \\ \lambda_1^{-c_2} & \lambda_2^{-c_2} & \dots & \lambda_k^{-c_2} \\ \vdots & \vdots & \ddots & \vdots \\ \lambda_1^{-c_k} & \lambda_2^{-c_k} & \dots & \lambda_k^{-c_k} \end{bmatrix} $$$

Let's denote its determinant as $$$D_{c_1, \dots, c_k}(\lambda_1, \dots, \lambda_k)$$$, then the solution is given as

$$$ \alpha_i = \dfrac{D_{c_1,\dots,c_k}(\lambda_1, \dots, \lambda_{i-1}, \color{red}{1}, \lambda_{i+1}, \dots, \lambda_k)}{D_{c_1,\dots,c_k}(\lambda_1, \dots, \lambda_{i-1}, \color{blue}{\lambda_i}, \lambda_{i+1}, \dots, \lambda_k)}. $$$

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

Tags math, fibonacci, linear recurrence

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en11 English adamant 2022-04-10 03:20:24 21
en10 English adamant 2022-04-10 03:16:50 798
en9 English adamant 2022-04-10 03:15:31 439 problem example
en8 English adamant 2022-04-03 19:19:12 114
en7 English adamant 2022-04-03 18:06:20 10
en6 English adamant 2022-04-03 18:05:46 150
en5 English adamant 2022-04-03 17:52:40 1453
en4 English adamant 2022-04-03 17:25:23 226
en3 English adamant 2022-04-03 17:21:14 737
en2 English adamant 2022-04-03 17:12:46 765
en1 English adamant 2022-04-03 03:59:30 2446 Initial revision (published)