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

and

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.