Page 569 - Discrete Mathematics and Its Applications

548 8 / Advanced Counting Techniques

Expanding the right-hand side of this equation into partial fractions (as is done in the integration
of rational functions studied in calculus) gives

1 1 1
G(x) = + .
2 1 − 8x 1 − 10x
Using Example 5 twice (once with a = 8 and once with a = 10) gives
∞ ∞
1
n n
n n
G(x) = 8 x + 10 x
2
n = 0 n = 0
∞
1 n n n
= (8 + 10 )x .
2
n = 0
Consequently, we have shown that
1
n
n
a n = (8 + 10 ).
2 ▲

Proving Identities via Generating Functions

In Chapter 6 we saw how combinatorial identities could be established using combinatorial
proofs. Here we will show that such identities, as well as identities for extended binomial coef-
ficients, can be proved using generating functions. Sometimes the generating function approach
is simpler than other approaches, especially when it is simpler to work with the closed form
of a generating function than with the terms of the sequence themselves. We illustrate how
generating functions can be used to prove identities with Example 18.

EXAMPLE 18 Use generating functions to show that

n
2
C(n, k) = C(2n, n)
k = 0
whenever n is a positive integer.

2n
n
Solution: First note that by the binomial theorem C(2n, n) is the coefficient of x in (1 + x) .
However, we also have
n 2
(1 + x) 2n =[(1 + x) ]
2
n 2
=[C(n, 0) + C(n, 1)x + C(n, 2)x + ··· + C(n, n)x ] .
n
The coefficient of x in this expression is
C(n, 0)C(n, n) + C(n, 1)C(n, n − 1) + C(n, 2)C(n, n − 2) + ··· + C(n, n)C(n, 0).

n 2
This equals k = 0 C(n, k) , because C(n, n − k) = C(n, k). Because both C(2n, n) and
n 2 n 2n ▲
k = 0 C(n, k) represent the coefficient of x in (1 + x) , they must be equal.
Exercises 42 and 43 ask that Pascal’s identity and Vandermonde’s identity be proved using
generating functions.