Page 438 - Discrete Mathematics and Its Applications

6.4 Binomial Coefficients and Identities 417

12 13
Consequently, the coefficient of x y in the expansion is obtained when j = 13, namely,

25 12 13 25! 12 13
2 (−3) =− 2 3 .
13 13! 12! ▲
We can prove some useful identities using the binomial theorem, as Corollaries 1, 2, and 3
demonstrate.

COROLLARY 1 Let n be a nonnegative integer. Then

n
n n
= 2 .
k
k = 0

Proof: Using the binomial theorem with x = 1 and y = 1, we see that

n n
n n
n n k n−k
2 = (1 + 1) = 1 1 = .
k k
k = 0 k = 0
This is the desired result.
There is also a nice combinatorial proof of Corollary 1, which we now present.

n
Proof: A set with n elements has a total of 2 different subsets. Each subset has zero elements,
n
n

one element, two elements,..., or n elements in it. There are 0 subsets with zero elements, 1
n
n

subsets with one element, subsets with two elements,..., and subsets with n elements.
2 n
Therefore,
n
n
k
k = 0
counts the total number of subsets of a set with n elements. By equating the two formulas we
have for the number of subsets of a set with n elements, we see that
n
n n
= 2 .
k
k = 0
COROLLARY 2 Let n be a positive integer. Then

n
k n
(−1) = 0.
k
k = 0

Proof: When we use the binomial theorem with x =−1 and y = 1, we see that

n n
n n
n n k n−k k
0 = 0 = ((−1) + 1) = (−1) 1 = (−1) .
k k
k = 0 k = 0
This proves the corollary.