Page 439 - Discrete Mathematics and Its Applications

418 6 / Counting

Remark: Corollary 2 implies that
n n n n n n

+ + + ··· = + + + ··· .
0 2 4 1 3 5

COROLLARY 3 Let n be a nonnegative integer. Then

n
k n n
2 = 3 .
k
k = 0

n
Proof: We recognize that the left-hand side of this formula is the expansion of (1 + 2) provided
by the binomial theorem. Therefore, by the binomial theorem, we see that

n n
n n
n n−k k k
(1 + 2) = 1 2 = 2 .
k k
k = 0 k = 0
Hence
n
k n n
2 = 3 .
k
k = 0

Pascal’s Identity and Triangle

The binomial coefficients satisfy many different identities. We introduce one of the most im-
portant of these now.

THEOREM 2 PASCAL’S IDENTITY Let n and k be positive integers with n ≥ k. Then

n + 1 n n

= + .
k k − 1 k

Proof: We will use a combinatorial proof. Suppose that T is a set containing n + 1 elements. Let
n+1
a be an element in T , and let S = T −{a}. Note that there are subsets of T containing k
k
elements. However, a subset of T with k elements either contains a together with k − 1 elements
n
of S, or contains k elements of S and does not contain a. Because there are subsets of
k−1
n
k − 1 elements of S, there are subsets of k elements of T that contain a. And there are
k−1
n n

k subsets of k elements of T that do not contain a, because there are k subsets of k elements
of S. Consequently,

n + 1 n n
= + .
k k − 1 k
Remark: It is also possible to prove this identity by algebraic manipulation from the formula
n

for (see Exercise 19).
r