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. |
No comments:
Post a Comment