Page 567 - Discrete Mathematics and Its Applications

546 8 / Advanced Counting Techniques

Using the extended binomial theorem and Example 8, we have
n
G(x) = x /(1 − x) n
n
= x · (1 − x) −n
∞
−n
n r
= x (−x)
r
r = 0
∞
r r r
n
= x (−1) C(n + r − 1,r)(−1) x
r = 0
∞

= C(n + r − 1,r)x n+r
r = 0
∞
t
= C(t − 1,t − n)x
t = n
∞
r
= C(r − 1,r − n)x .
r = n
We have shifted the summation in the next-to-last equality by setting t = n + r so that t = n
when r = 0 and n + r − 1 = t − 1, and then we replaced t by r as the index of summation in
the last equality to return to our original notation. Hence, there are C(r − 1,r − n) ways to
select r objects of n different kinds if we must select at least one object of each kind. ▲

Using Generating Functions to Solve Recurrence Relations

We can find the solution to a recurrence relation and its initial conditions by finding an explicit
formula for the associated generating function. This is illustrated in Examples 16 and 17.

EXAMPLE 16 Solve the recurrence relation a k = 3a k−1 for k = 1, 2, 3,... and initial condition a 0 = 2.

∞ k
a
Solution: Let G(x) be the generating function for the sequence {a k }, that is, G(x) = k = 0 k x .
First note that
∞ ∞

k
xG(x) = a k x k+1 = a k−1 x .
k = 0 k = 1
Using the recurrence relation, we see that

∞ ∞
k k
G(x) − 3xG(x) = a k x − 3 a k−1 x
k = 0 k = 1
∞
k
= a 0 + (a k − 3a k−1 )x
k = 1
= 2,

because a 0 = 2 and a k = 3a k−1 . Thus,

G(x) − 3xG(x) = (1 − 3x)G(x) = 2.