- 1 Volume 1
- 1.1 Chapter 1: Basic Concepts: Fibonacci Number
- 1.2 Chapter 1: Basic Concepts: Generating Functions
- 1.2.1 Addition
- 1.2.2 Shifting
- 1.2.3 Generating Functions for Linearly Recurrent Series
- 1.2.4 Multiplication
- 1.2.5 Generating Function for Sum of Terms of Sequence
- 1.2.6 Products of Three Functions
- 1.2.7 Recurrence Relations with Binomial Coefficients
- 1.2.8 Calculus
- 1.2.9 Functions With Known Generating Functions
- 2 Example Problems
- 3 Related
- 4 Flags
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:
(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, :
Now combining these facts we can eliminate terms on the RHS:
This simplifies to:
Now the vertical asymptotes of this rational function are at the roots of the denominator, which in this case are:
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:
we can get to the partial fraction expansion:
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:
Note that this comes from our other identities, also derived using the method above (the first is the Maclaurin Series):
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:
which, because , gives us a very good approximation for the nth Fibonacci number:
Chapter 1: Basic Concepts: Generating Functions
For an alternative approach/additional coverage of generating functions, see 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
Addition of two generating functions involves adding the respective terms of their series (i.e., adding the coefficients of each term of the series together). Can also multiply by constant, which carries through to each term.
If we wish to shift the generating function from to we can do so by multiplying the entire generating function by z.
This generalizes, to multiplying by x^k to shift each coefficient k terms to the right.
The last summation can be extended over all so long as for .
Generating Functions for Linearly Recurrent Series
Given any linearly recurrent sequence, where
the resulting generating function is a polynomial divided by the quantity
For example, if we consider the simplest possible sequence,
This gives us our important formula:
which is equivalent to the Maclaurin series.
Multiplying two series together involves lots of possible interactions of terms, so we define this by supposing we have two generating functions,
then we can define the product as the sequence that generates :
Generating Function for Sum of Terms of Sequence
Suppose we have a sequence and we wish to determine the total sum of the terms.
If we evaluate the multiplication expression, given above, and we use , we actually end up with the following series:
for which , from which it follows that:
which means that the expression
is the generating function for the sums of the original sequence'.
Products of Three Functions
Knuth also defines more general products of three generating functions, or even n generating functions.
Recurrence Relations with Binomial Coefficients
When the recurrence relation involves binomial coefficients, we often want a generating function for our sequence that is given by:
Better, instead, to use generating functions for the sequences:
This is because:
where (Note that this formula is symmetric, since .)
We can also use the derivative and integral operations on the generating functions to define
Likewise, the integration operation yields:
Special case: compute these quantities for the most basic generating function,
Applying the summation identities on the right side, we get the derivative equal to:
and the integral equal to:
Functions With Known Generating Functions
There are some functions for which we explicitly know the power series expansion, and we can write the generating function for a particular sequence. These are often useful to combine with the above operations to extend the kinds of series and sequences we can deal with.
- Binomial theorem
- Exponential series
- Logarithm series
Note that when r is a negative integer, we get the special case already encountered:
The exponential series is defined by:
For logarithm series, we can use
Knuth AOCP Section 1.2.9 Exercise 1
Exercise 1. What is the generating function for ?
For this problem, don't be fooled by the complexity of the preceding section - it's back to the basics. This sequence of numbers looks a lot like, oh, I dunno, two sequences of numbers added together. Specifically,
2 4 8 16 32 3 9 27 81 243
If we can find the generating function for 2^n, and find the generating function for 3^n, we can use the addition property of generating functions to combine them.
To find the generating function for :
Now subtracting the first and last quantities gives:
which yields the generating function for :
Repeating the process for gives:
Now to get the overall generating function for we add these two functions together and combine into a single rational expression:
Now for the cool part. If we do a Taylor Series expansion of , we can compute simply by obtaining the coefficient of the Taylor Series polynomial. While this may seem like a pointless mathematical trick for a function like , the real utility of the method comes when we apply this approach to much more general functions.
If we evaluate the 500th term of the Taylor Series expansion, which we can denote , we get:
which, in case you did not already notice, is
See also: more notes on generating functions (an alternate presentation that is a little more intuition-based than Knuth's examples):
Other books covering generating functions include:
The Art of Computer Programmingnotes from reading Donald Knuth's Art of Computer Programming
Part of the 2017 CS Study Plan.
Volume 2: Seminumerical Algorithms
Volume 3: Sorting and Searching
Flags · Template:AOCPFlag · e