Basis change in Fibonacci numbers

Правка en4, от adamant, 2022-04-03 17:25:23

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}. $$$
Теги math, fibonacci, linear recurrence

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en11 Английский adamant 2022-04-10 03:20:24 21
en10 Английский adamant 2022-04-10 03:16:50 798
en9 Английский adamant 2022-04-10 03:15:31 439 problem example
en8 Английский adamant 2022-04-03 19:19:12 114
en7 Английский adamant 2022-04-03 18:06:20 10
en6 Английский adamant 2022-04-03 18:05:46 150
en5 Английский adamant 2022-04-03 17:52:40 1453
en4 Английский adamant 2022-04-03 17:25:23 226
en3 Английский adamant 2022-04-03 17:21:14 737
en2 Английский adamant 2022-04-03 17:12:46 765
en1 Английский adamant 2022-04-03 03:59:30 2446 Initial revision (published)