AOCP/Generating Functions

Before You Begin: Reading Notes

Knuth covers generating functions early in Volume 1, but with Knuth's Art of Computer Programming books, the length has no correlation to the difficulty. Some sections are long and can be skipped entirely with no impact, others are critical to and referenced throughout the entire 3-volume series.

The sections preceding Generating Functions are crucial to understanding all of the material Knuth covers, but particularly to understanding generating functions. You absolutely, positively must read the preceding sections to follow Knuth's coverage of generating functions. There are a number of subtle steps that he moves through quite fast, as he is covering a huge amount of material. The generating functions section integrates material from 8 prior sections, which also cover a huge amount of material very fast. So there are many explicit and passing references to prior material.

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{aligned}G(z)&=&F_{0}+F_{1}z+F_{2}z^{2}+\dots \\&=&z+z^{2}+2z^{3}+3z^{4}+\dots \end{aligned}}$

(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$:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle z = \phi, \hat{\phi} }

where

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle z^2 + z - 1 = (\phi + z)( \hat{\phi} + z) }

we can get to the partial fraction expansion:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G(z) = \dfrac{1}{\sqrt{5}} \left( \dfrac{1}{1 - \phi z} - \dfrac{1}{1 - \hat{\phi} z} \right) }

where again

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \dfrac{1}{1 - \phi z} = 1 + \phi z + \phi^2 z^2 + \phi^3 z^3 + \dots }

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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):

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F_n = \dfrac{1}{\sqrt{5}} \left( \phi^n - \hat{\phi}^n \right) }

which, because Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \hat{\phi}^n << 1} , gives us a very good approximation for the nth Fibonacci number:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F_n \approx \dfrac{\phi^n}{\sqrt{5}} \quad \mbox{correct to nearest integer} }

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
  • Miscellaneous

Addition

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.

Shifting

If we wish to shift the generating function from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_0 a_1 a_2 \dots} to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 0 a_0 a_1 a_2} 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.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle z^n \sum_{k \geq 0} a_k z^k = \sum_{k \geq n} z^k }

The last summation can be extended over all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k \geq 0} so long as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_k = 0} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k < 0} .

Generating Functions for Linearly Recurrent Series

Given any linearly recurrent sequence, where

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_n = c_1 a_{n-1} + \dots + c_m a_{n-m} }

the resulting generating function is a polynomial divided by the quantity

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (1 - c_1 z - \dots - c_m z^m) }

For example, if we consider the simplest possible sequence,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{align} G(z) & \rightarrow & 1, 1, 1, \dots \\ z G(z) & \rightarrow & 0, 1, 1, \dots \end{align} }

and therefore

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (1 - z) G(z) = 1 }

This gives us our important formula:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \dfrac{1}{1 - z} = 1 + z + z^2 + \dots }

which is equivalent to the Maclaurin series.

Multiplication

Multiplying two series together involves lots of possible interactions of terms, so we define this by supposing we have two generating functions,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{align} G_1(z) &=& a_0 + a_1 z + a_2 z^2 + \dots \\ G_2(z) &=& b_0 + b_1 z + b_2 z^2 + \dots \end{align} }

then we can define the product as the sequence that generates :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G_1(z) G_2(z) \rightarrow s_1, s_2, s_3, \dots, s_n }

where

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_n = \sum_{k=0}^{n} a_k b_{n-k} }

Generating Function for Sum of Terms of Sequence

Suppose we have a sequence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G(z) = a_0 + a_1 z + a_2 z^2 + \dots} and we wish to determine the total sum of the terms.

If we evaluate the multiplication expression, given above, and we use Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b_i = 1} , we actually end up with the following series:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \dfrac{1}{1 - z} = 1 + z + z^2 + \dots }

for which Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b_i = 1} , from which it follows that:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \dfrac{1}{1 - z} G(z) = a_0 + (a_0 + a_1) z + (a_0 + a_1 + a_2) z^2 + \dots }

which means that the expression

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \dfrac{1}{1-z} G(z) }

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_0, c_1, \dots} that is given by:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_n = \sum_{k} \binom{n}{k} a_k b_{n-k} }

Better, instead, to use generating functions for the sequences:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{align} \displaystyle{ \langle \frac{a_n}{n!} \rangle, \langle \frac{b_n}{n!} \rangle, \langle \frac{c_n}{n!} \rangle } \end{align} }

This is because:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left( \frac{a_0}{0!} + \frac{a_1}{1!} + \frac{a_2}{2!} + \dots \right) \left( \frac{b_0}{0!} + \frac{b_1}{1!} + \frac{b_2}{2!} + \dots \right) = \left( \frac{c_0}{0!} + \frac{c_1}{1!} + \frac{c_2}{2!} + \dots \right) }

where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_n = \sum_k \binom{n}{k} a_k b_{n-k}} (Note that this formula is symmetric, since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \binom{n}{k} = \binom{n}{n-k}} .)

Calculus

We can also use the derivative and integral operations on the generating functions to define

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G'(z) = a_1 + 2 a_2 z + 3 a_3 z^2 + \dots = \sum_{k \geq 0} (k+1) a_{k+1} z^k }

Likewise, the integration operation yields:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \int_{t=0}^{z}{G(t) dt} = a_0 z + \dfrac{1}{2} a_1 z^2 + \dfrac{1}{3} a_2 z^3 + \dots = \sum_{k \geq 1} \dfrac{1}{k} a_{k-1} z^k }

Special case: compute these quantities for the most basic generating function,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \dfrac{1}{1-z} = 1 + z + z^2 + z^3 + z^4 + \dots }

Applying the summation identities on the right side, we get the derivative equal to:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{align} \dfrac{d}{dx} \left( \dfrac{1}{1-x} \right) &=& \dfrac{1}{(1-x)^2} \\ &=& 1 + 2z + 3z^2 + \dots \\ &=& \sum_{k \geq 0} (k+1) z^k \end{align} }

and the integral equal to:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{align} \int_{0}^{z}{ \dfrac{1}{1-t} dt } &=& \ln{\left(\dfrac{1}{1-z}\right)} \\ &=& z + \frac{1}{2} z^2 + \frac{1}{3} z^3 + \dots \\ &=& \sum_{k \geq 1} \dfrac{1}{k} z^k \end{align} }

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.

Most important:

• Binomial theorem
• Exponential series
• Logarithm series
• Others

Binomial Theorem

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (1 + z)^r = 1 + rz + \dfrac{r(r-1)}{2} z^2 + \dots = \sum_{k \geq 0} \binom{r}{k} z^k }

Note that when r is a negative integer, we get the special case already encountered:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \dfrac{1}{(1-z)^{n+1}} = \sum_{k \geq 0} \binom{n+k}{n} z^k }

Exponential Series

The exponential series is defined by:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e^z = 1 + z + \dfrac{1}{2!} z^2 + \dots = \sum_{k \geq 0} \dfrac{1}{k!} z^k }

Logarithm Series

For logarithm series, we can use

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ln{(1+z)} = z - \dfrac{1}{2} z^2 + \dfrac{1}{3} z^3 - \dots = \sum_{k \geq 1} \dfrac{(-1)^{k+1}}{k} z^k }

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ln{ \left( \dfrac{1}{1-z} \right) } = z + \dfrac{1}{2} z^2 + \dfrac{1}{3} z^3 + \dots = \sum_{k \geq 1} \dfrac{1}{k} z^k }

Example Problems

AOCP Exercises

Knuth AOCP Section 1.2.9 Exercise 1

Exercise 1. What is the generating function for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2^n} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (1-2z) G_{2^n}(z) = 1 + 0 + 0 + 0 + \dots }

which yields the generating function for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2^n} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G_{2^n}(z) = \dfrac{1}{1 - 2z} }

Repeating the process for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 3^n} gives:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G_{3^n}(z) = \dfrac{1}{1 - 3z} }

Now to get the overall generating function for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \langle 2^n + 3^n \rangle} we add these two functions together and combine into a single rational expression:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G(z)} , we can compute Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2^n + 3^n} simply by obtaining the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n^{th}} coefficient of the Taylor Series polynomial. While this may seem like a pointless mathematical trick for a function like Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G_n(z)[500]} , we get:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{align} G_n(z)[500] = 3636029179586993684238526707954331911802338502600162304034603583258060 \\ 0191583895484198511536369996679450049715724100683352008148159059109207 \\ 7819142079301219138181759224025267202176687407229640966567179316611617 \\ 95984554271383193123905199377 \end{align} }

which, in case you did not already notice, is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2^{500} + 3^{500}}

Related

See also: more notes on generating functions (an alternate presentation that is a little more intuition-based than Knuth's examples):

Generating Functions

Other books covering generating functions include:

• Analytic Combinatorics
• Applied Combinatorics