240 Sets, Combinatorics, and Probability
PRACTICE42 Expand (jc + l)5 using the binomial theorem. \342\226\240
The theorem
binomial tells us that term k + 1 in the expansion of (a + b)n is
C(n, k)a\"~kbk. This allows us to find individual terms in the expansion without computing the
entire expression.
PRACTICE 43 What is the fifth term in the expansion of (jc + y)7? m
By using various values for a and b in the binomial theorem, certain identities can be
obtained.
EXAMPLE 70 Let a = b = 1 in the binomial theorem. Then
(1 + 1)\"
=
C(n, 0) + C(n, 1) + - + C(n, k) + - + C(n, ri)
or
2\" =
C(n, 0) + C(n, 1) + - + C(n, k) +
- + C(n, n) (2)
Actually, equation (2) can be proved on its own using a combinatorial proof. The number
C(n, k), the number of ways to select k items from a set of n items, can be thought of as the
number of fc-element subsets of an n-element set. The right side of equation (2) therefore
represents the total number of all the subsets (of all sizes) of an n-elementset. But we already
know that the number of such subsetsis 2\". m
Section 3.6 Review
Technique
Use
\342\226\240 the binomial theorem to expand a binomial.
Use
\342\226\240 the binomial theorem to find a particular term in the expansion of a binomial.
Main Ideas
The
\342\226\240 binomial theorem provides a formula for expanding a binomial without multiplying it
out.
The
\342\226\240 coefficients of a binomial raised to a nonnegative integer power are combinations of n
items as laid out in row n of Pascal's triangle.
Exercises 3.6
1. Expand the expression using the binomial theorem.
(a +
\342\200\242a. b)5 b. (jc + yf *c. (a + 2)5
d. (a - 4)4 *e. (2x + 3y)3 f. (3jc - l)5
g. -
3qf h. Ux +
(2p
^Y
Section3.6 Binomial Theorem 241
In Exercises 2-9, find the indicated term in the expansion.
2. The fourth in (a + b)10
term
3. The seventh in (jc - y)n
term
The
\342\200\2424. sixth term in (2x - 3)9
5. The fifth term in (3a + lb)1
*6. The last term in (jc
\342\200\224
3y)%
7. The last term in (ab + 3x)6
The
\342\200\2428. third term in (4jc - 2y)5
( - iY>
9. The fourth term in 3jc I
^
10. Use the binomial theorem (morethan once) to expand (a + b + c)3.
11. Expand (1 + 0.1)5 in order to compute (l.l)5.
*12. What is the coefficient ofx3yA in the expansion of (2x \342\200\224
y + 5)8?
13. What is the coefficient of xsy2z2 in the expansion of (jc + y + 2z)9?
14. Prove that
C(n + 2, r) = C(n,r) + 2C(n, r
-
1) + C(n, r - 2) for 2 < r < n
(///nf: Use Pascal's formula.)
15. Provethat
C(k, k) + C(fc + 1,k) + - + C(n, A:)
=
C(n + 1, k + 1) foi| 0 < A: < n
(Hint: Use induction on n for a fixed, arbitrary k, as well as Pascal's formula.)
16. Use the binomial theorem to provethat
C(n, 0)
-
C(n, 1) + C(n, 2)
- - + (-l)\"C(n,n) =* 0
* 17. Use the binomial theorem to prove that
C(n, 0) + C(n, 1)2 + C(n, 2)22 + - + C(n, n)2n = 3\"
18. a. Use the binomial theorem to provethat
C(n, n) + C(n, n
-
1)2 + C(n, n -
2)22 + - + C(n, 1)2\"-' + C(n, 0)2\" = 3\"
b. Prove this result directly from Exercise 17.
19. a. Expand (1 + x)n.
b. Differentiate both sides of the equation from part (a) with respect to jc to obtain
n(\\ + jc)\"\"1
=
C(n, 1) + 2C(n, 2)x + 3C(n, 3)jc2 + - + nC(n, n)x\"~l
c. Prove that
C(n, 1) + 2C(n,2) + 3C(n, 3) + - + nC(n, n) = n2\"~1
d. Prove that
C(n, 1)
-
2C(n, 2) + 3C(n, 3)
-
4C(n, 4) +- + (-\\)\"-lnC(n, n)
= 0
242 Sets, Combinatorics, and Probability
20. a. Prove that
2\302\253+i
= + - +
1) +
pj-j- C(n,n)
C(n, 0) +
^j-p | C(n,
| C(n, 2)
b. Prove that
1
n+ 1
C(n, 0) - | CK 1) +
| C(n, 2) + - + (- D\"
^j-
C(n, n)
{Hint: Integrate both sides of the equation from part (a) of Exercise 19.)
21. The general form of the principle of inclusion and exclusion is
|A1u--uAj= 2 \\Ai\\~ 2 |A,nA,.|
lsi<jsn
+ 2 \\A.nAjnA,}
II ^ /CI
- \342\200\242\342\200\242\342\200\242
+(-l)\"+1|A,
v 7 I 1
n \342\200\242\342\200\242\342\200\242
nA I
\302\253l (1)
This exercise provides
an alternate to the inductive proof given in Section 3.3 of the
principle of inclusionand exclusion. The equation is correct \342\200\242 x
if for any jc in {Ax u \342\200\242
\342\200\242
u An},
is countedexactly once by the right side of the equation.
a. Suppose jc is an element of k of the n sets {Ap ... ,AJ. Let B equal the set of A.s of
which jc is a member. Then jc is counted once in the right side of (1) for each of
the intersections that include only members of B. Show that in the intersections of m
members of {Av ... , AJ, 1 < m ^ k, there are C(k, m) that include only members
offl.
b. Usingthe result of part (a), write a sum of terms that represents the number of times x
is counted in the right side of (1).
c. UseExercise 16 to show that this sum of terms equals 1.
Chapter 3 Review
Terminology
addition principle (p. 192) countable set (p. 176)
binary operation (p. 169) decision tree (p. 195)
binomial coefficient (p. 239) denumerable set (p. 176)
binomial theorem (p. 238) disjoint sets (p. 172)
Cantor'sdiagonalization method (p. 177) dual of a set identity (p. 175)
cardinality of a set (p. 175) empty set (p. 165)
Cartesian product (cross product) of sets equal sets (p. 164)
(p. 173) event (p. 223)
closedset under an operation (p. 169) expectedvalue (p. 229)
combination (p. 211) finite set (p. 164)
combinatorial proof (p. 237) independent events (p. 228)
combinatorics (p. 188) infinite set (p. 164)
complement of a set (p. 171) intersection of sets (p. 171)
conditional probability (p. 227) multiplication principle (p. 189)
