Section 4.5 Binomial Theorem
295
If we compute the numerical values of the expressions, we see that Pascal’s triangle has the form
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Observing this figure, it is clear that the outer edges are all 1s. But it also seems
that any element not on the outer edge can be obtained by adding together the two
elements directly above it in the preceding row (for example, the first 10 in row
five is below the first 4 and the 6 of row four). If this relationship is indeed always
true, it means that
C(n, k) = C(n − 1, k − 1) + C(n − 1, k) for 1 ≤ k ≤ n − 1
(1)
Equation (1) is known as Pascal’s formula.
To prove Pascal’s formula, we begin with the right side:
C(n − 1, k − 1) + C(n − 1, k) =
(n − 1)!
(k − 1)! 3n − 1 − (k − 1) 4!
+
(n − 1)!
k!(n − 1 − k)!
=
(n − 1)!
(k − 1)!(n − k)!
+
(n − 1)!
k!(n − 1 − k)!
=
k(n − 1)!
k!(n − k)!
+
(n − 1)!(n − k)
k!(n − k)!
(multiplying the first term by k/k and the second term by (n − k)/(n − k))
=
k (n − 1)! + (n − 1)!(n − k)
k!(n − k)!
(adding fractions)
=
(n − 1)! 3k + (n − k) 4
k!(n − k)!
(factoring the numerator)
=
(n − 1)!(n)
k!(n − k)!
=
n!
k!(n − k)!
= C(n, k)