Section 4.5 Binomial Theorem
297
As the inductive hypothesis, we assume that
(a + b)
k
= C(k, 0)a
k
b
0
+ C(k, 1)a
k−1
b
1
+ c + C(k, k − 1)a
1
b
k−1
+ C(k, k)a
0
b
k
Now consider
(a + b)
k+1
= (a + b)
k
(a + b) = (a + b)
k
a + (a + b)
k
b
= 3C(k, 0)a
k
b
0
+ C(k, 1)a
k−1
b
1
+ c + C(k, k − 1)a
1
b
k−1
+ C(k, k)a
0
b
k
4a + 3C(k, 0)a
k
b
0
+ C(k, 1)a
k−1
b
1
+ c + C(k, k − 1)a
1
b
k−1
+ C(k, k)a
0
b
k
4b
(by the inductive hypothesis)
= C(k, 0)a
k+1
b
0
+ C(k, 1)a
k
b
1
+ c + C(k, k − 1)a
2
b
k−1
+ C(k, k)a
1
b
k
+ C(k, 0)a
k
b
1
+ C(k, 1)a
k−1
b
2
+ c + C(k, k − 1)a
1
b
k
+ C(k, k)a
0
b
k+1
= C(k, 0)a
k+1
b
0
+ 3C(k, 0) + C(k, 1) 4a
k
b
1
+ 3C(k, 1) + C(k, 2) 4a
k−1
b
2
+ c + 3C(k, k − 1) + C(k, k) 4a
1
b
k
+ C(k, k)a
0
b
k+1
(collecting like terms)
= C(k, 0)a
k+1
b
0
+ C(k + 1, 1)a
k
b
1
+ C(k + 1, 2)a
k−1
b
2
+ c + C(k + 1, k)a
1
b
k
+ C(k, k)a
0
b
k+1
(using Pascal’s formula)
= C(k + 1, 0)a
k+1
b
0
+ C(k + 1, 1)a
k
b
1
+ C(k + 1, 2)a
k−1
b
2
+ c + C(k + 1, k)a
1
b
k
+ C(k + 1, k + 1)a
0
b
k+1
(because C(k, 0) = 1 = C(k + 1, 0) and C(k, k) = 1 = C(k + 1, k + 1))
This completes the inductive proof of the binomial theorem.
The binomial theorem also has a combinatorial proof. Writing (a + b)
n
as (a + b)(a + b) c (a + b) (n factors), we know that the answer (using the distributive law of numbers) is the sum of all values obtained by multiplying each term in
a factor by a term from every other factor. For example, using b as the term from k
factors and a as the term from the remaining n − k factors produces the expression
a
n−k
b
k
. Using b from a different set of k factors and a from the n − k remaining factors also produces a
n−k
b
k
. How many such terms are there? There are C(n, k) different
ways to select k factors from which to use b; hence there are C(n, k) such terms. After
adding these terms together, the coefficient of a
n−k
b
k
is C(n, k). As k ranges from 0
to n, the result of summing the terms is the binomial theorem.
Because of its use in the binomial theorem, the expression C(n, r) is also
known as a binomial coefficient.
297
As the inductive hypothesis, we assume that
(a + b)
k
= C(k, 0)a
k
b
0
+ C(k, 1)a
k−1
b
1
+ c + C(k, k − 1)a
1
b
k−1
+ C(k, k)a
0
b
k
Now consider
(a + b)
k+1
= (a + b)
k
(a + b) = (a + b)
k
a + (a + b)
k
b
= 3C(k, 0)a
k
b
0
+ C(k, 1)a
k−1
b
1
+ c + C(k, k − 1)a
1
b
k−1
+ C(k, k)a
0
b
k
4a + 3C(k, 0)a
k
b
0
+ C(k, 1)a
k−1
b
1
+ c + C(k, k − 1)a
1
b
k−1
+ C(k, k)a
0
b
k
4b
(by the inductive hypothesis)
= C(k, 0)a
k+1
b
0
+ C(k, 1)a
k
b
1
+ c + C(k, k − 1)a
2
b
k−1
+ C(k, k)a
1
b
k
+ C(k, 0)a
k
b
1
+ C(k, 1)a
k−1
b
2
+ c + C(k, k − 1)a
1
b
k
+ C(k, k)a
0
b
k+1
= C(k, 0)a
k+1
b
0
+ 3C(k, 0) + C(k, 1) 4a
k
b
1
+ 3C(k, 1) + C(k, 2) 4a
k−1
b
2
+ c + 3C(k, k − 1) + C(k, k) 4a
1
b
k
+ C(k, k)a
0
b
k+1
(collecting like terms)
= C(k, 0)a
k+1
b
0
+ C(k + 1, 1)a
k
b
1
+ C(k + 1, 2)a
k−1
b
2
+ c + C(k + 1, k)a
1
b
k
+ C(k, k)a
0
b
k+1
(using Pascal’s formula)
= C(k + 1, 0)a
k+1
b
0
+ C(k + 1, 1)a
k
b
1
+ C(k + 1, 2)a
k−1
b
2
+ c + C(k + 1, k)a
1
b
k
+ C(k + 1, k + 1)a
0
b
k+1
(because C(k, 0) = 1 = C(k + 1, 0) and C(k, k) = 1 = C(k + 1, k + 1))
This completes the inductive proof of the binomial theorem.
The binomial theorem also has a combinatorial proof. Writing (a + b)
n
as (a + b)(a + b) c (a + b) (n factors), we know that the answer (using the distributive law of numbers) is the sum of all values obtained by multiplying each term in
a factor by a term from every other factor. For example, using b as the term from k
factors and a as the term from the remaining n − k factors produces the expression
a
n−k
b
k
. Using b from a different set of k factors and a from the n − k remaining factors also produces a
n−k
b
k
. How many such terms are there? There are C(n, k) different
ways to select k factors from which to use b; hence there are C(n, k) such terms. After
adding these terms together, the coefficient of a
n−k
b
k
is C(n, k). As k ranges from 0
to n, the result of summing the terms is the binomial theorem.
Because of its use in the binomial theorem, the expression C(n, r) is also
known as a binomial coefficient.