Page 441 - Discrete Mathematics and Its Applications

420 6 / Counting

Other Identities Involving Binomial Coefficients

We conclude this section with combinatorial proofs of two of the many identities enjoyed by
the binomial coefficients.

THEOREM 3 VANDERMONDE’S IDENTITY Let m, n, and r be nonnegative integers with r not
exceeding either m or n. Then

r
m + n m n
= .
r r − k k
k = 0

Remark: This identity was discovered by mathematician Alexandre-Théophile Vandermonde
in the eighteenth century.

Proof: Suppose that there are m items in one set and n items in a second set. Then the total
m + n
number of ways to pick r elements from the union of these sets is .
r
Another way to pick r elements from the union is to pick k elements from the second set
and then r − k elements from the first set, where k is an integer with 0 ≤ k ≤ r. Because there
n
m
are ways to choose k elements from the second set and ways to choose r − k elements
k r − k
n
m
from the first set, the product rule tells us that this can be done in ways. Hence, the
r − k k
n
r m
total number of ways to pick r elements from the union also equals .
k = 0 r−k k
We have found two expressions for the number of ways to pick r elements from the
union of a set with m items and a set with n items. Equating them gives us Vandermonde’s
identity.
Corollary 4 follows from Vandermonde’s identity.
COROLLARY 4 If n is a nonnegative integer, then
2n n
n 2
= .
n k
k = 0

Proof: We use Vandermonde’s identity with m = r = n to obtain

2n n n n
n n 2
= = .
n n − k k k
k = 0 k = 0
n
n
The last equality was obtained using the identity = .
k n − k

ALEXANDRE-THÉOPHILE VANDERMONDE (1735–1796) Because Alexandre-Théophile Vandermonde was a sickly child, his
physician father directed him to a career in music. However, he later developed an interest in mathematics. His complete mathematical
work consists of four papers published in 1771–1772. These papers include fundamental contributions on the roots of equations, on
the theory of determinants, and on the knight’s tour problem (introduced in the exercises in Section 10.5). Vandermonde’s interest in
mathematics lasted for only 2 years. Afterward, he published papers on harmony, experiments with cold, and the manufacture of steel.
He also became interested in politics, joining the cause of the French revolution and holding several different positions in government.