Page 560 - Discrete Mathematics and Its Applications

8.4 Generating Functions 539

Remark: Theorem 1 is valid only for power series that converge in an interval, as all series
considered in this section do. However, the theory of generating functions is not limited to such
series. In the case of series that do not converge, the statements in Theorem 1 can be taken as
definitions of addition and multiplication of generating functions.

We will illustrate how Theorem 1 can be used with Example 6.

2
EXAMPLE 6 Let f(x) = 1/(1 − x) . Use Example 4 to find the coefficients a 0 ,a 1 ,a 2 ,... in the expansion
k
∞
a
f(x) = k = 0 k x .
Solution: From Example 4 we see that
2 3
1/(1 − x) = 1 + x + x + x + ··· .
Hence, from Theorem 1, we have

⎛ ⎞
∞ k ∞

2 k k
1/(1 − x) = ⎝ 1 x = (k + 1)x .
⎠
k = 0 j = 0 k = 0
▲
Remark: This result also can be derived from Example 4 by differentiation. Taking derivatives is
a useful technique for producing new identities from existing identities for generating functions.

To use generating functions to solve many important counting problems, we will need to
apply the binomial theorem for exponents that are not positive integers. Before we state an
extended version of the binomial theorem, we need to define extended binomial coefficients.

DEFINITION 2 Let u be a real number and k a nonnegative integer. Then the extended binomial coefficient
u

k is defined by

u u(u − 1) ··· (u − k + 1)/k! if k> 0,
=
k 1 if k = 0.

−2
1/2
EXAMPLE 7 Find the values of the extended binomial coefficients and .
3 3
Solution: Taking u =−2 and k = 3 in Definition 2 gives us

−2 (−2)(−3)(−4)
= =−4.
3 3!
Similarly, taking u = 1/2 and k = 3 gives us

1/2 (1/2)(1/2 − 1)(1/2 − 2)

=
3 3!
= (1/2)(−1/2)(−3/2)/6
= 1/16. ▲