Page 442 - Discrete Mathematics and Its Applications

6.4 Binomial Coefficients and Identities 421

We can prove combinatorial identities by counting bit strings with different properties, as
the proof of Theorem 4 will demonstrate.

THEOREM 4 Let n and r be nonnegative integers with r ≤ n. Then

n
n + 1 j
= .
r + 1 r
j = r

n + 1
Proof: We use a combinatorial proof. By Example 14 in Section 6.3, the left-hand side, ,
r + 1
counts the bit strings of length n + 1 containing r + 1 ones.
We show that the right-hand side counts the same objects by considering the cases corre-
sponding to the possible locations of the final 1 in a string with r + 1 ones. This final one must
occur at position r + 1, r + 2,..., or n + 1. Furthermore, if the last one is the kth bit there must
be r ones among the first k − 1 positions. Consequently, by Example 14 in Section 6.3, there
k − 1
are such bit strings. Summing over k with r + 1 ≤ k ≤ n + 1, we find that there are
r
n + 1 n
k − 1 j
=
r r
k = r + 1 j = r
bit strings of length n containing exactly r + 1 ones. (Note that the last step follows from the
change of variables j = k − 1.) Because the left-hand side and the right-hand side count the
same objects, they are equal. This completes the proof.

Exercises

1. Find the expansion of (x + y) 4 13. What is the row of Pascal’s triangle containing the bino-
9

a) using combinatorial reasoning, as in Example 1. mial coefficients k ,0 ≤ k ≤ 9?
b) using the binomial theorem.
n
n
14. Show that if n is a positive integer, then 1 = 0 < 1 <
2. Find the expansion of (x + y) 5 n n n
n
··· < = > ··· > n−1 > n = 1.
a) using combinatorial reasoning, as in Example 1.
n/2 n/2
n
n
b) using the binomial theorem. 15. Show that k ≤ 2 for all positive integers n and all in-
6
3. Find the expansion of (x + y) . tegers k with 0 ≤ k ≤ n.
13
5 8
4. Find the coefficient of x y in (x + y) . 16. a) Use Exercise 14 and Corollary 1 to show that if n is
n
n

5. How many terms are there in the expansion of (x + y) 100 an integer greater than 1, then ≥ 2 /n.

n/2
after like terms are collected? b) Conclude from part (a) that if n is a positive integer,
11
7
2n
6. What is the coefficient of x in (1 + x) ? then ≥ 4 /2n.
n
n
19
9
7. What is the coefficient of x in (2 − x) ? 17. Show that if n and k are integers with 1 ≤ k ≤ n, then
8 9
8. What is the coefficient of x y in the expansion of ≤ n /2 k−1 .
n
k
17
(3x + 2y) ? k
9. What is the coefficient of x 101 99 in the expansion of 18. Suppose that b is an integer with b ≥ 7. Use the bino-
y
(2x − 3y) 200 ? mial theorem and the appropriate row of Pascal’s triangle
4
k
∗ 10. Give a formula for the coefficient of x in the expansion to find the base-b expansion of (11) [that is, the fourth
b
of (x + 1/x) 100 , where k is an integer. power of the number (11) b in base-b notation].
n

k
∗ 11. Give a formula for the coefficient of x in the expansion 19. Prove Pascal’s identity, using the formula for r .
2
of (x − 1/x) 100 , where k is an integer. 20. Suppose that k and n are integers with 1 ≤ k< n. Prove
12. The row of Pascal’s triangle containing the binomial co- the hexagon identity
10

efficients ,0 ≤ k ≤ 10, is:
k n − 1 n n + 1 n − 1 n n + 1
= ,
1 10 45 120 210 252 210 120 45 10 1 k − 1 k + 1 k k k − 1 k + 1
Use Pascal’s identity to produce the row immediately fol- which relates terms in Pascal’s triangle that form a
lowing this row in Pascal’s triangle. hexagon.