ACOP/Generating Functions

Knuth: Volume 1: Fundamental Algorithms

Chapter 1: Basic Concepts: Generating Functions

You absolutely, positively must read the preceding chapters to follow Knuth here. There are a number of subtle steps that he moves through quite fast, about as quickly as he moves through the other material, except he's now integrating his method of presenting all 8 prior sections, including both explicit and passing references to prior material.

As with the binomial coefficients...

Example Problems

Knuth AOCP Section 1.2.9 Exercise 1

Exercise 1. What is the generating function for $ <2^n + 3^n> = \{ 2, 5, 13, 35, \dots \} $?

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 $ 2^n $:

$ \begin{align} G_{2^n}(z) &=& 1 + 2z + 4z^2 + \dots \\ z G_{2^n}(z) &=& 0 + z + 2z^2 + \dots \\ 2z G_{2^n}(z) &=& 0 + 2z + 4z^2 + \dots \end{align} $

Now subtracting the first and last quantities gives:

$ (1-2z) G_{2^n}(z) = 1 + 0 + 0 + 0 + \dots $

which yields the generating function for $ 2^n $:

$ G_{2^n}(z) = \dfrac{1}{1 - 2z} $

Repeating the process for $ 3^n $ gives:

$ G_{3^n}(z) = \dfrac{1}{1 - 3z} $

Now to get the overall generating function for $ <2^n + 3^n> $ we add these two functions together and combine into a single rational expression:

$ G(z) = \dfrac{1}{1-2z} + \dfrac{1}{1 - 3z} = \dfrac{2-5x}{1-5x+6x^2} $

Now for the cool part. If we do a Taylor Series expansion of $ G(z) $, we can compute $ 2^n + 3^n $ simply by obtaining the $ n^{th} $ coefficient of the Taylor Series polynomial. While this may seem like a pointless mathematical trick for a function like $ 2^n + 3^n $, the real utility of the method comes when we apply this approach to much more general functions.