The Art and Craft of Problem Solving

4.3 GENERATING FUNCTIONS 137

We claim that A(x)B(x) is the generating function for the sequence Uo, Ul, U 2 ,' ... This

isn't hard to see if you pondered the "red and blue" discussion above: After all, each

term in A(x) has the form x^2 a where a is a nonnegative integer, and likewise, each term

in B(x) has the form �b. Hence all the terms in the product A(x)B(x) will be terms

with exponents of the form 2a + 5b. Each different pair (a, b) that satisfies 2a + 5b = n

will produce the monomial XZ in the product A(x)B(x). Hence the coefficient of XZ will

be the number of different solutions to 2a + 5b = n.

Now we use the geometric-series tool to simplify

Thus

1

A(x) =

1 - x^2

and

1

B(x) = -- 5 '

I-x

(^123)
(^2 )(
(^5) ) =UO +U1X+U 2 X +U 3 X + ....
1 - x I-x
(4)
In an abstract sense, we are "done," for we have a nice form for the generating

function. But we haven't the slightest idea what UIOO equals! This isn't too hard to

find. By inspection, we can compute

Uo = U 2 = U4 = Us = U 6 = U 7 = (^1) and Ul = U 3 = O.
Then we transform (4) into
1 = (1 -x^2 ) (1 - Y) ( Uo + U 1 x + U 2 x^2 + U 3 x^3 + ... )
= (1 - x^2 - Y + x^7 ) ( Uo + U 1 x + U 2 x^2 + U 3 x^3 + ... ).
(5)
The l' coefficient of the product of the terms on the right-hand side must be zero

(if k > 0). Multiplying out, this coefficient is

So for all k > 7, we have the recurrence relation

(6)

It is a fairly simple, albeit tedious, exercise to compute UIOO by using (5) and (6). For

example,

etc. If you play around with this, you will find some shortcuts (try working back­
ward, and/or make a table to help eliminate some steps), and eventually you will get

U 100 = 11. •

The next example does not concern itself with computing the coefficient of a gen­
erating function, but rather solves a problem by equating two generating functions­
one ugly, one pretty.