From charlesreid1

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 \langle2^n + 3^n\rangle = \{ 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:

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

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 \langle 2^n + 3^n \rangle 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.


If we evaluate the 500th term of the Taylor Series expansion, which we can denote G_n(z)[500], we get:

G_n(z)[500] = 3636029179586993684238526707954331911802338502600162304034603583258060 \\
0191583895484198511536369996679450049715724100683352008148159059109207 \\
7819142079301219138181759224025267202176687407229640966567179316611617 \\

which, in case you did not already notice, is 2^{500} + 3^{500}