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:
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)$$$:
Therefore, our equation above is, equivalent to the following:
The determinant of this system of equations is $$$a^{-p}b^{-q} - a^{-q}b^{-p}$$$. Solving the system, we get the solution
Multiplying numerators and denominators by $$$a^q b^q$$$ for $$$\alpha$$$ and $$$a^p b^p$$$ for $$$\beta$$$, we get a nicer form:
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
Substituting it back into $$$\alpha$$$ and $$$\beta$$$, we get
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)$$$:
Therefore, we have a system of equations
For this system, the determinant is $$$\frac{q-p}{a^{p+q+1}}$$$ and the solution is
Another interesting way to get this solution is via L'Hôpital's rule:
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
This system of equations has a following matrix:
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
Unfortunately, on practice in makes more sense to find $$$\alpha_i$$$ with the Gaussian elimination rather than with these direct formulas.
how you are so good at math?
I'm not really, I just like doing weird stuff as a hobby.
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. :(
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.