Page 568 - Discrete Mathematics and Its Applications

8.4 Generating Functions 547

∞ k k
Solving for G(x) shows that G(x) = 2/(1 − 3x). Using the identity 1/(1 − ax) = a x ,
k = 0
from Table 1, we have
∞ ∞
k k k k
G(x) = 2 3 x = 2 · 3 x .
k = 0 k = 0

k
Consequently, a k = 2 · 3 . ▲

EXAMPLE 17 Suppose that a valid codeword is an n-digit number in decimal notation containing an even
number of 0s. Let a n denote the number of valid codewords of length n. In Example 4 of
Section 8.1 we showed that the sequence {a n } satisfies the recurrence relation

a n = 8a n−1 + 10 n−1

and the initial condition a 1 = 9. Use generating functions to find an explicit formula for a n .

Solution: To make our work with generating functions simpler, we extend this sequence
by setting a 0 = 1; when we assign this value to a 0 and use the recurrence relation, we
0
have a 1 = 8a 0 + 10 = 8 + 1 = 9, which is consistent with our original initial condition. (It
also makes sense because there is one code word of length 0—the empty string.)
n
We multiply both sides of the recurrence relation by x to obtain
n
n
a n x = 8a n−1 x + 10 n−1 n
x .
∞ n

a
Let G(x) = n = 0 n x be the generating function of the sequence a 0 ,a 1 ,a 2 ,.... We sum
both sides of the last equation starting with n = 1, to find that
∞ ∞
n n n−1 n

G(x) − 1 = a n x = (8a n−1 x + 10 x )
n=1 n=1
∞ ∞
n n−1 n
= 8 a n−1 x + 10 x
n=1 n=1
∞ ∞
n−1 n−1 n−1
= 8x a n−1 x + x 10 x
n=1 n=1
∞ ∞
n n n
= 8x a n x + x 10 x
n = 0 n = 0
= 8xG(x) + x/(1 − 10x),

where we have used Example 5 to evaluate the second summation. Therefore, we have

G(x) − 1 = 8xG(x) + x/(1 − 10x).

Solving for G(x) shows that

1 − 9x
G(x) = .
(1 − 8x)(1 − 10x)