AOCP/Generating Functions

Volume 1

Chapter 1: Basic Concepts: Generating Functions

Knuth's Fibonacci Example

In Section 1.2.8, on Fibonacci Numbers (see AOCP/Fibonacci Numbers), Knuth demonstrates a procedure that he goes into greater detail about in Section 1.2.8.

(This is one aspect of Knuth's book you learn very fast - it is impossible to jump into the book at an arbitrary point, because Knuth uses so much custom, self-defined notation, and introduces it so subtly and casually, and so continually, that by page 15 you're lost if you haven't read pages 1-14.)

Knuth discusses the Fibonacci numbers. Then, he says, let's construct an infinite series that's going to look like this:

$ \begin{align} G(z) &=& F_0 + F_1 z + F_2 z^2 + \dots \\ &=& z + z^2 + 2z^3 + 3z^4 + \dots \end{align} $

(Note this uses the convention that F0 = 0 and F1 = 1 for the Fibonacci series, not the usual 1 and 1).

As Knuth states: "We have no reason to believe a priori this series will exist, but we will be optimistic."

I like this approach a lot.

So, we're after the generating function of the Fibonacci numbers, $ \langle F_n \rangle $:

$ \begin{align} z G(z) = F_0 z + F_1 z^2 + F_2 z^3 + \dots \\ z^2 G(z) = F_0 z^2 + F_1 z^3 + F_2 z^4 + \dots \end{align} $

Now combining these facts we can eliminate terms on the RHS:

$ (1 - z - z^2) G(z) = F_0 + (F_1 - F_0) z + (F_2 - F_1 - F_0) z^2 + (F_3 - F_2 - F_1) z^3 + \dots $

This simplifies to:

$ \begin{align} (1 - z - z^2) G(z) &=& z \\ G(z) &=& \dfrac{z}{(1 - z - z^2)} \end{align} $

Now the vertical asymptotes of this rational function are at the roots of the denominator, which in this case are:

$ z = \phi, \hat{\phi} $

where

$ \hat{\phi} = 1 - \phi $

and phi is the Golden Ratio. See Phi.

Expanding this function using a Taylor series expansion will yield the polynomial whose coefficients are the Fibonacci series.

Utilizing the Fibonacci Generating Function

There are a couple of ways that we can now use this generating function.

=Partial Fraction Expansion

Knuth begins by expanding the result using partial fractions. Starting with the factorization of the bottom term:

$ z^2 + z - 1 = (\phi + z)( \hat{\phi} + z) $

we can get to the partial fraction expansion:

$ G(z) = \dfrac{1}{\sqrt{5}} \left( \dfrac{1}{1 - \phi z} - \dfrac{1}{1 - \hat{\phi} z} \right) $

where again

$ \hat{\phi} = 1 - \phi $

This tells us something about the overall sequence: if the generating function is the sum of two terms, that means the sequence is the sum of two sequences. Specifically, these two:

$ \dfrac{1}{1 - \phi z} = 1 + \phi z + \phi^2 z^2 + \phi^3 z^3 + \dots $

$ \dfrac{1}{1 - \hat{\phi} z} = 1 + \hat{\phi} z + \hat{\phi}^2 z^2 + \hat{\phi}^3 z^3 + \dots $

Note that this comes from our other identities, also derived using the method above (the first is the Maclaurin Series):

$ \begin{align} \dfrac{1}{1 - z} &=& 1 + z + z^2 + z^3 + \dots \\ \dfrac{1}{1 - az} &=& = 1 + az + a^2 z^2 + a^3 z^3 + \dots \end{align} $

Closed Form Expression for Approx Nth Fib Number

We can actually obtain a closed-form expression for an approximation of the nth Fibonacci number if we take this analysis just one step further:

$ G(z) = \dfrac{1}{\sqrt{5}} \left( ( 1 + \phi z + \phi^2 z^2 + \dots ) - ( 1 + \hat{\phi} z + \hat{\phi}^2 z^2 ) \right) $

This yields:

$ F_n = \dfrac{1}{\sqrt{5}} \left( \phi^n - \hat{\phi}^n \right) $

which, because $ \hat{\phi}^n << 1 $, gives us a very good approximation for the nth Fibonacci number:

$ F_n \approx \dfrac{\phi^n}{\sqrt{5}} \quad \mbox{correct to nearest integer} $