Basis change in Fibonacci numbers

Правка en2, от adamant, 2022-04-03 17:12:46

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?

Теги 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)