The Fibonacci generating function
The recurrence relation for the Fibonacci sequence is ubiquitous:
for and .
Suppose we want to know the th Fibonacci number ( without dealing with all the recursion above. How can that be found?
What follows is a neat derivation for using generating functions. The setup was taken from both Cormen, Leiserson and Rivest (1st Edition), and Wilf’s “Generating Functionology.” If you’d like to fill in the blanks in their derivations, best stop reading here! Otherwise, let’s see how it works.
Suppose we want the generatiing function for the Fibonacci sequence
By definition, the generating function
This isn’t particularly helpful, let’s get a better solution for , we’ll multiply by :
Subtracting 2 from 1 gives us
You should see a nice, closed form solution now:
Interesting, but not useful. We can go further, let’s work out a partial fraction decomposition.
First we determine the roots of the equation
which for easier factoring we want to write as
By the quadratic formula, we find the roots
Note that , and . To check the result, plug the roots back into the equation:
Now that we have the roots, we can decompose the Fibonacci generating function into its constituent fractions. However, for reasons which will become apparent shortly, let’s do a little more work to rewrite the factors into a convenient form. Starting with the factors above,
Note that and and substitute to obtain
Using partial fraction decomposition,
and we can write
Solving first for , let :
After convincing yourself that , it’s easy to see
By similar computation,
The end result of these computations produces the very useful
Continuing, recall for
Choose where and write
resulting in an expression for the th coefficient, that is, the th Fibonacci number:
That’s all for now.