adamant's blog

Basis change in linear recurrences
By adamant, history, 2 years ago, In English

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$$$?

Timus — Fibonacci Sequence. The sequence $$$F$$$ satisfies the condition $$$F_n = F_{n-1} + F_{n-2}$$$. You're given $$$F_i$$$ and $$$F_j$$$, compute $$$F_n$$$.

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

102129D - Basis Change. The sequence $$$F$$$ satisfies $$$F_n=\sum\limits_{i=1}^k a_i F_{n-i}$$$. Find $$$c_1,\dots,c_n$$$ such that $$$F_n = \sum\limits_{i=1}^k c_i F_{n-b_i}$$$.

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_1^{-c_1} = 1,\\ \alpha_1 \lambda_2^{-c_2}+\dots+\alpha_k \lambda_2^{-c_k} = 1,\\ \dots\\ \alpha_1 \lambda_k^{-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_1^{-c_2} & \dots & \lambda_1^{-c_k} \\ \lambda_2^{-c_1} & \lambda_2^{-c_2} & \dots & \lambda_2^{-c_k} \\ \vdots & \vdots & \ddots & \vdots \\ \lambda_k^{-c_1} & \lambda_k^{-c_2} & \dots & \lambda_k^{-c_k} \end{bmatrix} $$$

Matrices of this kind are called alternant matrices. Let's denote its determinant as $$$D_{\lambda_1, \dots, \lambda_k}(c_1, \dots, c_k)$$$, then the solution is

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

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

  • Vote: I like it
  • +172
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +29 Vote: I do not like it

how you are so good at math?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    I'm not really, I just like doing weird stuff as a hobby.

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

I'm not sure if I understand correctly. since $$$p \neq q$$$ one of $$$F_{q-p}$$$ and $$$F_{p-q}$$$ has a negative index. What does that mean?

Also, in order to define $$$F_n=\alpha F_{n−p}+\beta F_{n−q}$$$ the first $$$r=max(p, q)$$$ elements have to be defined (the same way as for the Fibonacci sequence the first 2 elements need to be defined.). But then looking at $$$F_{r+1}$$$ and inserting it in your final formula the result depends only on the first $$$r$$$ elements (and the one number with negative index. Is that key here?). So the information about $$$\alpha$$$ and $$$\beta$$$ seems lost in $$$F_{r+1}$$$ (since the first $$$r$$$ elements hold no Information about them, except maybe the one with negative index). And inductivly the Information seems lost on every following element. I don't understand that.

For the usual Fibonacci series we have $$$\alpha=\beta=1$$$ and $$$q=1$$$ and $$$p=2$$$. $$$F_1=F_2=1$$$. Inserting in your formula yields $$$F_n=F_1 F_{n-2} / F_{-1} + F_2 F_{n-1} / F_{1}=F_{n-2} / F_{-1} + F_{n-1}$$$. So I assume $$$F_{-1}=1$$$ has to hold here? Why? Edit: Oh yes, inserting $$$-1$$$ into Binets formula indeed does yield 1. I'm stil confused about $$$\alpha$$$ and $$$\beta$$$ supposedly disappearing. :(

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    It means that we can invert $$$F_n = F_{n-1}+F_{n-2}$$$ to $$$F_n = F_{n+2}-F_{n+1}$$$ and get Fibonacci numbers with negative indices. It would hold that $$$F_{-n} =(-1)^{n+1}F_n$$$.

    I wanted to find $$$\alpha$$$ and $$$\beta$$$ that would work for any sequence that initially adhered to the recurrence. That is, we know that $$$F_n = r F_{n-1} + s F_{n-2}$$$ and we find $$$\alpha$$$ and $$$\beta$$$ such that for all such sequences $$$F_n = \alpha F_{n-p}+\beta F_{n-q}$$$ is also true.

    → Reply