AOCP/Generating Functions

Volume 1

Chapter 1: Basic Concepts: Fibonacci Number

Knuth begins his coverage of generating functions in preceding section to the generating functions section. When he discusses Fibonacci numbers, he demonstrates the procedure below, which he specifically calls out as "extremely important."

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} $

Chapter 1: Basic Concepts: Generating Functions

Just as he did with AOCP/Binomial Coefficients, after introducing the definition a generating function and its history, Knuth extensively details all of the operations that we can perform on these generating functions:

• Addition of generating functions
• Shifting generating function coefficients
• Multiplication of generating functions
• Change of variable in z (even or odd coefficients only)
• Differentiation and integration
• Known generating functions
  • Binomial theorem
  • Exponential series
  • Logarithm series
  • Miscellaneous