Page 440 - Discrete Mathematics and Its Applications

6.4 Binomial Coefficients and Identities 419

() 1
0
0
() () 1 1
1
1
0
1
() () () By Pascal's identity: 1 2 1
2
2
2
2
0
1
() () () () () () () 1 3 3 1
7
3
3
3
6
6
3
=
+
2
1
5
4
3
5
0
() () () () () 1 4 6 4 1
4
4
4
4
4
4
2
3
0
1
() () () () () () 1 5 10 10 5 1
5
5
5
5
5
5
5
3
4
0
1
2
() () () () () () () 1 6 15 20 15 6 1
6
6
6
6
6
6
6
3
5
0
6
1
4
2
() () () () () () () () 1 7 21 35 35 21 7 1
7
7
7
7
7
7
7
7
1
4
7
2
3
5
6
0
() () () () () () () () () 1 8 28 56 70 56 28 8 1
8
8
8
8
8
8
8
8
8
1
0
3
4
6
5
8
7
2
... ...
(a) (b)
FIGURE 1 Pascal’s Triangle.
n
n

Remark: Pascal’s identity, together with the initial conditions = = 1 for all integers n,
0 n
can be used to recursively define binomial coefficients. This recursive definition is useful in the
computation of binomial coefficients because only addition, and not multiplication, of integers
is needed to use this recursive definition.
Pascal’s identity is the basis for a geometric arrangement of the binomial coefficients in a
triangle, as shown in Figure 1.
The nth row in the triangle consists of the binomial coefficients

n
,k = 0, 1,...,n.
k
This triangle is known as Pascal’s triangle. Pascal’s identity shows that when two adjacent
binomial coefficients in this triangle are added, the binomial coefficient in the next row between
these two coefficients is produced.
BLAISE PASCAL (1623–1662) Blaise Pascal exhibited his talents at an early age, although his father, who
had made discoveries in analytic geometry, kept mathematics books away from him to encourage other interests.
At 16 Pascal discovered an important result concerning conic sections.At 18 he designed a calculating machine,
which he built and sold. Pascal, along with Fermat, laid the foundations for the modern theory of probability. In
this work, he made new discoveries concerning what is now called Pascal’s triangle. In 1654, Pascal abandoned
his mathematical pursuits to devote himself to theology. After this, he returned to mathematics only once. One
night, distracted by a severe toothache, he sought comfort by studying the mathematical properties of the cycloid.
Miraculously, his pain subsided, which he took as a sign of divine approval of the study of mathematics.