Sunday, 14 July 2024

Fibonacci Generating Functions

The Fibonacci Sequence can be generated from the following recurrence relation:$$a(n)=a(n-1)+a(n-2) \text{ with } a(0)=1 \text{ and } a(1)=1$$The generating function for this series is given by:$$ \frac{x^2}{1-x-x^2} $$How is generating function affected if we have a recurrence relation as follows:$$a(n)=a(n-1)+a(n-8)$$I created a post about this titled Fibonacci-like Sequences quite recently on May 13th 2024. The new generating function is now:$$ \frac{x^2}{1-x-x^8} $$What if there are coefficients (let's say \( \alpha \) and \( \beta \) in front of the two terms on the LHS:$$a(n) = \alpha . a(n-1) + \beta . a(n-2)$$In this case, the generating function becomes: $$ \frac{x^2}{1-\alpha . x - \beta . x^2}$$Let's take the following example:$$a(n)=4. \, a(n-1)+10. \, a(n-2)$$The generating function becomes$$ \frac{x^2}{1-4x - 10 x^2}$$The sequence of terms becomes (permalink):

0, 1, 4, 26, 144, 836, 4784, 27496, 157824, 906256, 5203264, 29875616, 171535104, 984896576, 5654937344, 32468715136, 186424233984, 1070384087296, 6145778689024, 35286955629056

This numbers form the initial terms of OEIS A180226:


 A180226



a(n) = 4*a(n-1) + 10*a(n-2), with a(1)=0 and a(2)=1.



To check what happens to the generating function when the tribonacci sequence is considered, see my post titled Beyond Fibonacci (March 10th 2019).

No comments:

Post a Comment