Basis change in Fibonacci numbers

Revision en1, by adamant, 2022-04-03 03:59:30

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

$$$P(x) \equiv P(a) \frac{x-b}{a-b} + P(b) \frac{x-a}{b-a}\mod{(x-a)(x-b)}.$$$

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

$$$ (1-\alpha a^{-p} - \beta a^{-q})(x-b) = (1-\alpha b^{-p} - \beta b^{-q}) (x-a). $$$

Equating coefficients near $$$x^1$$$ and $$$x^0$$$, we get the following system:

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

Substituting $$$a \mapsto a^{-1}$$$ and $$$b \mapsto b^{-1}$$$, we get it a bit simplified:

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

The determinant of this system of equations is $$$(a-b)(a^pb^q - a^qb^p)$$$. Solving the system, we get the solution

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

Doing the back-substitute $$$a \mapsto a^{-1}$$$ and $$$b \mapsto b^{-1}$$$, we get a somewhat 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?

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)