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{array}
G(z) &=& F_0 + F_1 z + F_2 z^2 + \dots \\
&=& z + z^2 + 2z^3 + 3z^4 + \dots
\end{array}
</math>

(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{array} 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{array}  $

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{array} (1 - z - z^2) G(z) &=& 1 \\ G(z) &=& \dfrac{1}{(1 - z - z^2)} \end{array}  $

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.