300
Sets, Combinatorics, and Probability
17. Use the binomial theorem to prove that
C(n, 0) − C(n, 1) + C(n, 2) − c + (− 1)
n
C(n, n) = 0
18. Use the binomial theorem to prove that
C(n, 0) + C(n, 1)2 + C(n, 2)2
2
+ c + C(n, n)2
n
= 3
n
19. Use the binomial theorem to prove that
C(n, n) + C(n, n − 1)2 + C(n, n − 2)2
2
+ c + C(n, 1)2
n−1
+ C(n, 0)2
n
= 3
n
20. Prove the result of Exercise 19 directly from Exercise 18.
21. (Requires calculus)
a. Expand (1 + x)
n
.
b. Differentiate both sides of the equation from part (a) with respect to x to obtain
n(l + x)
n−1
= C(n, 1) + 2C(n, 2)x + 3C(n, 3)x
2
+ c + nC(n, n)x
n−1
c. Prove that
C(n, 1) + 2C(n, 2) + 3C(n, 3) + c + nC(n, n) = n2
n−1
d. Prove that
C(n, 1) − 2C(n, 2) + 3C(n, 3) − 4C(n, 4) + c + (−1)
n−1
nC(n, n) = 0
22. (Requires calculus)
a. Prove that
2
n+1
− 1
n + 1
= C(n, 0) +
1
2
C(n, 1) +
1
3
C(n, 2) + c +
1
n + 1
C(n, n)
b. Prove that
1
n + 1
= C(n, 0) −
1
2
C(n, 1) +
1
3
C(n, 2) + c + (−1)
n
1
n + 1
C(n, n)
(Hint: Integrate both sides of the equation from part (a) of Exercise 21.)
23. The general form of the principle of inclusion and exclusion is
0 A 1 c c c A n 0 = ∙
1≤i≤n
0 A i 0 − ∙
1≤i 0 A i d A j 0
+
∙
1≤i 0 A i d A j d A k 0
− c + (−1)
n+1
0 A 1 d c d A n 0
(1)