Pascal’s Triangle
In Chapter 10, we established the Binomial Theorem (BT) which states that for all non-negative integers n,
Let us display the binomial coefficients row by row following the increasing values of n as shown in Figure 12.1. We observe from Figure 12.1 the following.
1. The binomial coefficient at a lattice point counts the number of shortest routes from the top lattice point (representing 
) to the lattice point concerned. For example, there are 
(= 6) shortest routes from the lattice point representing to the lattice point (also see Example 5.1).
Figure 12.1
2. The number pattern is symmetric with respect to the vertical line through the rop lattice point, and this observation corresponds to the identity 
(see (10.2)).
3. Any binomial coefficient represented by an interior lattice point is equal to the sum of the two binomial coefficients represented by the lattice points on its “shoulders” (see Figure 12.2). This observation corresponds to the identity 
(see (10.3)).
Figure 12.2
4. The sum of the binomial coefficients in the nth row is equal to 2n and this fact corresponds to the identity
The number pattern of Figure 12.1 was known to Omar Khayyam and Jia Xian around 1100 AD. The pattern was also found in the book written by the Chinese mathematician Yang Hui in 1261, in which Yang Hui called it, the Jia Xian triangle. The number pattern in the form of Figure 12.3 was found in another book written by another Chinese mathematician Zhu Shijie in 1303.
However, the number pattern of Figure 12.1 is generally called Pascal’s Triangle in memory of the great French mathematician Blaise Pascal (1623-1662) who also applied the “triangle” to the study of probability, a subject dealing with “chance”. For a history of this number pattern, readers are referred to the book Pascal’s Arithmetical Triangle by A. W. F. Edwards (Oxford University Press
Figure 12.3
Blaise Pascal
Look at Pascal’s triangle of Figure 12.4.
What is the sum of the six binomial coefficients enclosed in the shaded rectangle? The answer is 56. Note that this answer appears as another binomial coefficient located on the right of 21 in the next row. Is this situation just a coincidence? Let us take a closer look.
Figure 12.4
Observe that
by applying the identity 
Figure 12.5
Figure 12.6
The above result is really a special case of a general situation. As a matter of fact, the above argument can also be used to establish the following general result (see also Figure 12.5):
By the symmetry of Pascal’s triangle, one obtains the following accompanying identity of (B4) (see also Figure 12.6):
A second look at Figures 12.5 and 12.6 will make us easily realise why (B4) and (B5) are often called the “Hockey Stick Identities”.
To end this chapter, we show an application of Identity (B4) in the solution of the following problem which appeared in International Mathematical Olympiad 1981.
Example 12.1 Let 1 ≤ r ≤ n and consider all r-element subsets of the set {1,2,... ,n}. Each of these subsets has a smallest member. Let F(n,r) denote the arithmetic mean of these smallest numbers. Prove that
Solution As an illustration of this problem, we consider the case when n = 6 and r = 4. There are 
4-element subsets of the set {1,2,3,4,5,6}. They and their “smallest members” are listed in Table 12.1.
Table 12.1
and this is equal to 
when n = 6 and r = 4.
Write 
n = {1,2,..., n}. To evaluate F(n, r), it is clear that we need to first find out
1. which numbers in n could be the smallest member of an r-element subset of n (in the above example, these are 1, 2, 3 but not 4, 5, 6), and
2. how many times such a smallest member occurs (in the above example, 1 occurs ten times, 2 four times and 3 once);
and then sum these smallest numbers up, and finally divide by 
, the number of r-element subsets of n, to obtain the “average”.
The last r elements (according to the magnitude) of the set n are:
It follows that n – r + 1 is the largest possible number to be the smallest member of an r-element subset of n. Hence, 1,2,3,... ,n – r + 1 are all the possible candidates to be the smallest members of r-element students of n.
Let k ∈ {1,2,3,... ,n – r + 1}. Our next task is to find out how many times k occurs as the smallest member. To form an r-element subset of n containing k as the smallest member, we simply form an (r–1)-element subset from the (n–k)-element set {k+1, k+2,... ,n} and then add k to it. The number of (r – 1)-element subsets of {k + 1,k + 2,. ..,n} is given by 
Thus, k occurs times as the smallest member. Let Σ denote the sum of all these smallest members. Then, as k = 1,2,...,n – r + 1, we have
Now, by applying (B4) to each summand above except the last one and noting that 
can be simplified to
By applying (B4) once again, we have
Finally, by definition of F(n,r), it follows that
as desired.
12.1 Find the coefficient of x5 in the expansion of
12.2 Find the coefficient of x3 in the expansion of
where n is a natural number with n ≥ 4.
12.3 Consider the rows of Pascal’s Triangle. Prove that if the nth row is made into a single number by using each element as a digit of the number (carrying over when an element itself has more than one digit), the number is equal to 11n–1. (For example, from the first row 1 = 110, from the second row 11 = 111, from the third row 121 = 112, and from the 6th row 15(10)(10)51 = 15(11)051 = 161051 = 115.)
12.4 On the rth day of an army recruitment exercise, r men register themselves. Each day, the recruitment officer chooses exactly k of the men and line them up in a row to be marched to the barracks. Show that the sum of the numbers of all the possible rows in the first 2k days is equal to the number of possible rows in the (2k + 1)th day.
12.5 The greatest integer not exceeding a real number x is denoted by 
Show that
(i)
(ii) 
with equality if and only if 
is odd.
12.6 Evaluate 
12.7 Find the number of non-negative integer solutions to
in the following two ways:
(i) Consider the cases when RHS = 0,1,2,..., 30.
(ii) Consider the situation of distributing a suitable number of identical objects into 5 distinct boxes.
Hence, use a similar approach to prove the Hockey Stick
Identity (B4).
12.8 In Pascal’s Triangle, there is a row where you can find three consecutive terms x, y, z such that x : y : z = 4:5:6. Which row is it? Which terms are they?
