296
Sets, Combinatorics, and Probability
Another, less algebraic way to prove Pascal’s formula involves a counting argument; hence it is called a combinatorial proof. We want to compute C(n, k),
the number of ways to choose k objects from n objects. There are two disjoint
categories of such choices—item 1 is one of the k objects or it is not. If item 1 is
one of the k objects, then the remaining k − 1 objects must come from the remaining n − 1 objects exclusive of item 1, and there are C(n − 1, k − 1) ways for this
to happen. If item 1 is not one of the k objects, then all k objects must come from
the remaining n − 1 objects, and there are C(n − 1, k) ways for this to happen.
The total number of outcomes is the sum of the number of outcomes from these
two disjoint cases.
Once we have Pascal’s formula for our use, we can develop the formula for
(a + b)
n
, known as the binomial theorem.
Binomial theorem and its Proof
In the expansion of (a + b)
2
, a
2
+ 2ab + b
2
, the coefficients are 1, 2, and 1, which
is row 2 in Pascal’s triangle.
Looking at the coefficients in the expansion of (a + b)
2
, (a + b)
3
, and (a + b)
4
suggests a general result, which is that the coefficients in the expansion of (a + b)
n
look like row n in Pascal’s triangle. This is indeed the binomial theorem.
PraCtiCe 39 Compute the expansion for (a + b)
3
and (a + b)
4
and compare the coefficients with rows 3
and 4 of Pascal’s triangle.
■
tHeoRem BiNOmial theORem
For every nonnegative integer n,
(a + b)
n
= C(n, 0)a
n
b
0
+ C(n, 1)a
n−1
b
1
+ C(n, 2)a
n−2
b
2
+ c + C(n, k)a
n−k
b
k
+ c + C(n, n − 1)a
1
b
n−1
+ C(n, n)a
0
b
n
= ∙
n
k=0
C(n, k)a
n−k
b
k
Because the binomial theorem is stated “for every nonnegative integer n,” a proof
by induction seems appropriate. For the basis step, n = 0, the theorem states
(a + b)
0
= C(0, 0)a
0
b
0
which is
1 = 1
Since this is certainly true, the basis step is satisfied.
ReminDeR
The expansion of (a + b)
n
starts with a
n
b
0
. From
there the power of a goes
down and the power of b
goes up, but for each term
the powers of a and b add
up to n. The coefficients
are all of the form
C(n, the power of b).
Sets, Combinatorics, and Probability
Another, less algebraic way to prove Pascal’s formula involves a counting argument; hence it is called a combinatorial proof. We want to compute C(n, k),
the number of ways to choose k objects from n objects. There are two disjoint
categories of such choices—item 1 is one of the k objects or it is not. If item 1 is
one of the k objects, then the remaining k − 1 objects must come from the remaining n − 1 objects exclusive of item 1, and there are C(n − 1, k − 1) ways for this
to happen. If item 1 is not one of the k objects, then all k objects must come from
the remaining n − 1 objects, and there are C(n − 1, k) ways for this to happen.
The total number of outcomes is the sum of the number of outcomes from these
two disjoint cases.
Once we have Pascal’s formula for our use, we can develop the formula for
(a + b)
n
, known as the binomial theorem.
Binomial theorem and its Proof
In the expansion of (a + b)
2
, a
2
+ 2ab + b
2
, the coefficients are 1, 2, and 1, which
is row 2 in Pascal’s triangle.
Looking at the coefficients in the expansion of (a + b)
2
, (a + b)
3
, and (a + b)
4
suggests a general result, which is that the coefficients in the expansion of (a + b)
n
look like row n in Pascal’s triangle. This is indeed the binomial theorem.
PraCtiCe 39 Compute the expansion for (a + b)
3
and (a + b)
4
and compare the coefficients with rows 3
and 4 of Pascal’s triangle.
■
tHeoRem BiNOmial theORem
For every nonnegative integer n,
(a + b)
n
= C(n, 0)a
n
b
0
+ C(n, 1)a
n−1
b
1
+ C(n, 2)a
n−2
b
2
+ c + C(n, k)a
n−k
b
k
+ c + C(n, n − 1)a
1
b
n−1
+ C(n, n)a
0
b
n
= ∙
n
k=0
C(n, k)a
n−k
b
k
Because the binomial theorem is stated “for every nonnegative integer n,” a proof
by induction seems appropriate. For the basis step, n = 0, the theorem states
(a + b)
0
= C(0, 0)a
0
b
0
which is
1 = 1
Since this is certainly true, the basis step is satisfied.
ReminDeR
The expansion of (a + b)
n
starts with a
n
b
0
. From
there the power of a goes
down and the power of b
goes up, but for each term
the powers of a and b add
up to n. The coefficients
are all of the form
C(n, the power of b).