Loading [MathJax]/jax/output/HTML-CSS/jax.js

Sunday, 14 July 2024

Fibonacci Generating Functions

The Fibonacci Sequence can be generated from the following recurrence relation:a(n)=a(n1)+a(n2) with a(0)=1 and a(1)=1The generating function for this series is given by:x21xx2How is generating function affected if we have a recurrence relation as follows:a(n)=a(n1)+a(n8)I created a post about this titled Fibonacci-like Sequences quite recently on May 13th 2024. The new generating function is now:x21xx8What if there are coefficients (let's say α and β in front of the two terms on the LHS:a(n)=α.a(n1)+β.a(n2)In this case, the generating function becomes: x21α.xβ.x2Let's take the following example:a(n)=4.a(n1)+10.a(n2)The generating function becomesx214x10x2The 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