Page 559 - Discrete Mathematics and Its Applications

538 8 / Advanced Counting Techniques

6
when x = 1. Consequently, G(x) = (x − 1)/(x − 1) is the generating function of the
sequence 1, 1, 1, 1, 1, 1. [Because the powers of x are only place holders for the terms of
the sequence in a generating function, we do not need to worry that G(1) is undefined.] ▲

EXAMPLE 3 Let m be a positive integer. Let a k = C(m, k), for k = 0, 1, 2,...,m. What is the generating
function for the sequence a 0 ,a 1 ,...,a m ?
Solution: The generating function for this sequence is

m
2
G(x) = C(m, 0) + C(m, 1)x + C(m, 2)x + ··· + C(m, m)x .
m
The binomial theorem shows that G(x) = (1 + x) . ▲

Useful Facts About Power Series

When generating functions are used to solve counting problems, they are usually considered to
be formal power series. Questions about the convergence of these series are ignored. However,
to apply some results from calculus, it is sometimes important to consider for which x the
power series converges. The fact that a function has a unique power series around x = 0 will
also be important. Generally, however, we will not be concerned with questions of convergence
or the uniqueness of power series in our discussions. Readers familiar with calculus can consult
textbooks on this subject for details about power series, including the convergence of the series
we consider here.
We will now state some important facts about infinite series used when working with
generating functions. A discussion of these and related results can be found in calculus texts.
EXAMPLE 4 The function f(x) = 1/(1 − x) is the generating function of the sequence 1, 1, 1, 1,..., be-
cause

2
1/(1 − x) = 1 + x + x + ···
for |x| < 1. ▲

2
3
EXAMPLE 5 The function f(x) = 1/(1 − ax) is the generating function of the sequence 1,a,a ,a ,...,
because
2 2
1/(1 − ax) = 1 + ax + a x + ···

when |ax| < 1, or equivalently, for |x| < 1/|a| for a = 0. ▲

We also will need some results on how to add and how to multiply two generating functions.
Proofs of these results can be found in calculus texts.

THEOREM 1 Let f(x) = ∞ a k ∞ b k
k = 0 k x . Then
k = 0 k x and g(x) =
⎛ ⎞
∞ ∞ k
k k
f(x) + g(x) = (a k + b k )x and f (x)g(x) = ⎝ a j b k−j ⎠ x .
k = 0 k = 0 j = 0