The Art and Craft of Problem Solving

4.3 GENERATING FUNCTIONS 133

• "Local" knowledge about the coefficients of a polynomial or power series f(x)

often provides "global" knowledge about the behavior of f(x), and vice versa.

The first fact is trivial, but it is the technical "motor" that makes things happen, for

it relates the addition of numbers and the multiplication of polynomials. The second

fact is deeper, and provides the motivation for doing what we are about to do.

Introductory Examples

Before we do anything, though, we need to define our subject. Given a (possibly

infinite) sequence aO,a) ,a 2 , ... , its generating function is

ao +a)x+a 2 x^2 + ....

Here are a few simple examples. We are assuming that you have a basic understanding

of sequences, polynomials, and simple summation formulas (Chapter 5), combina­

torics and the binomial theorem (Chapter 6), and infinite series (Chapters 5 and 9).

If you need to brush up in these areas, you may want to just skim this section now
and then reread it later. We do not recommend that you avoid this section altogether,
because the idea of generating functions is so powerful. The sooner you are exposed
to it, the better.

Example 4.3. 1 Let I = ao = a) = a 2 = .... Then the corresponding generating func­

tion is just

I+X+�+X^3 + ....

This is an infinite geometric series which converges to _

1

_, provided that Ixl < 1

I-x

(see page 160). In general, we don't worry too much about convergence issues with

generating functions. As long as the series converges for some values, we can usually

get by, as you will see below.

The infinite geometric series used above is ubiquitous in the world of generating

functions. Make a note of it; we shall call it the geometric series tool. Remember that

it works both ways: you probably have practice summing infinite geometric series, but

here's an example of the reverse direction. Study it carefully.

x

=

x

= (!) (x !�+�x^3 �x4 + ... )

2 +x 2 ( 1 - (-1x)) 2 2 22 23.

Example 4.3.2 For a fixed positive integer n, define the sequence ak = (:), k =

0, 1, 2 , ... ,n. The corresponding generating function is

(2)

by the binomial theorem. If we plug x = 1 into (2), we get the nice identity