Content

Pascal's triangle — the observations

We return to the observations made in the section A look at Pascal's triangle.

Observation 1

Each number in Pascal's triangle is the sum of the two numbers diagonally above it (with the exception of the 1s).

For example, from the fifth and fourth rows of Pascal's triangle, we have \(10 = 4+6\). In the notation introduced earlier in this module, this says

\[ \dbinom{5}{2} = \dbinom{4}{1} + \dbinom{4}{2}. \]

We now describe the general pattern.

Theorem (Pascal's identity)

\[ \dbinom{n}{r} = \dbinom{n-1}{r-1} + \dbinom{n-1}{r}, \qquad \text{for}\quad 0 < r < n. \] Proof \begin{align*} \dbinom{n-1}{r-1} + \dbinom{n-1}{r} &= \dfrac{(n-1)!}{(n-r)!(r- 1)!} + \dfrac{(n-1)!}{(n-1- r)!r!}\\ &= \dfrac{(n-1)!}{(n-r-1)!(r-1)!}\Bigg(\dfrac{1}{n-r} + \dfrac{1}{r}\Bigg)\\ &= \dfrac{(n-1)!}{(n-r-1)!(r-1)!}\Bigg(\dfrac{n}{(n-r)r} \Bigg)\\ &= \dfrac{n!}{(n-r)!r!}\\ &=\dbinom{n}{r}. \end{align*}

\(\Box\)

We will now undertake an alternative proof of Pascal's identity in a special case, but the general proof is essentially the same.

Let us start with a six-element set

\[ \{a,b,c,d,e,f\}. \]

The number of subsets with four elements is \(\dbinom{6}{4}\). Now let us single out the letter \(c\). The subsets with four elements can be separated into two types:

• the four-element sets that contain \(c\)
• the four-element sets that do not contain \(c\).

The number of four-element subsets that contain \(c\) is \(\dbinom{5}{3}\). The number of four-element subsets that do not contain \(c\) is \(\smash{\dbinom{5}{4}}\). Hence,

\[ \dbinom{6}{4} = \dbinom{5}{3} + \dbinom{5}{4}. \]

This gives us a combinatorial proof of Pascal's identity.

Application — number of paths across a grid

The following diagram shows a \(3 \times 3\) grid. The question arises as to how many paths there are from the bottom-left corner to the top-right corner of the grid, if you can only move to the right or up. We will call such moves 'forward' moves. One path from the bottom-left corner to the top-right corner is shown in red.

Detailed description of diagram

The numbers on the grid indicate the number of paths to that point. These numbers form part of Pascal's triangle. You can move up and across the grid using addition to find the number of paths to any point on the grid. For example:

• To get to the point Y you must go through point P or point X. There is one path to P and two paths to X. Therefore there are three paths to Y.

In the same way you can work out all the numbers in the grid, ending with the 20 paths from D to B.

There is a way to calculate the total number of paths directly. We can think of the paths as strings of letters. We will call a move one to the right \(R\) and a move one up \(U\). The path shown in the diagram is \(RURURU\). There are six moves in each string that take you from D to B. There must be three \(U\)'s and three \(R\)'s in each such string. If you choose where to place the three \(R\)'s in the string, then the remaining places must be filled with \(U\)'s. So there are \(\dbinom{6}{3} = 20\) paths from D to B.

This problem can be solved for an \(n\times n\) grid by thinking of the paths as strings of \(2n\) letters. It takes \(2n\) moves to go from the bottom-left corner of an \(n\times n\) grid to the top-right corner, and \(n\) of these moves are \(U\) and \(n\) are \(R\).

A path could be \(UUURRR\dots RUR\dots RR\). There are \(2n\) letters in the string and there are \(n\) \(U\)'s and \(n\) \(R\)'s. If you choose where to place the \(n\) \(R\)'s in the string, then the remaining places must be filled with \(U\)'s. There are \(\dbinom{2n}{n}\) ways of doing this and so, for an \(n\times n\) grid, there are \(\smash{\dbinom{2n}{n}}\) paths.

Observation 2

Each row of Pascal's triangle is symmetric.

Clearly

\[ \dbinom{n}{r} = \dbinom{n}{n-r}, \]

since choosing \(r\) objects from \(n\) objects leaves \(n-r\) objects, and choosing \(n-r\) objects leaves \(r\) objects. This means that the coefficient of \(x^r\) in the expansion of \((1+x)^n\) is the same as the coefficient of \(x^{n-r}\).

Observation 3

The sum of each row of Pascal's triangle is a power of 2. In fact, the sum of the entries in the \(n\)th row is \(2^n\).

Proof

We use the binomial theorem in the form

\[ (1+x)^n = \dbinom{n}{0}+ \dbinom{n}{1}x + \dbinom{n}{2}x^2+\dots+\dbinom{n}{r}x^r+\dots+ \dbinom{n}{n-1}x^{n-1} + \dbinom{n}{n}x^n. \]

Substituting \(x = 1\) gives

\[ 2^n = \dbinom{n}{0}+ \dbinom{n}{1} + \dbinom{n}{2}+\dots+\dbinom{n}{r}+\dots+ \dbinom{n}{n-1}+ \dbinom{n}{n}.\]

\(\Box\)

Application — Number of subsets of a set

There is another way of proving the observation above. Here is an example to illustrate the idea. There are three different chocolates \(A\), \(B\) and \(C\), and Alison can choose to eat whichever ones she wants. How many ways can this choice be made?

Let \(S=\{A,B,C\}\). The subsets are

\[ ø, \quad \{A\}, \quad \{B\}, \quad \{C\}, \quad \{A,B\}, \quad \{A,C\}, \quad \{B,C\}, \quad \{A,B,C\}. \]

There are

\begin{alignat*}{2} \dbinom{3}{0}&=1\text{ set with no elements},&\qquad \dbinom{3}{1}&=3 \text{ sets with one element},\\ \dbinom{3}{2}&=3 \text{ sets with two elements},&\qquad \dbinom{3}{3}&=1 \text{ set with three elements}. \end{alignat*}

Hence the total number of choices is

\[ \dbinom{3}{0}+\dbinom{3}{1}+\dbinom{3}{2}+\dbinom{3}{3}. \]

Now think of each chocolate one at a time:

• chocolate \(A\) can be chosen or not (2 ways)
• chocolate \(B\) can be chosen or not (2 ways)
• chocolate \(C\) can be chosen or not (2 ways).

So there are a total number of \(2^3 = 8\) ways of choosing chocolates (including not choosing any). This gives

\[ \dbinom{3}{0}+\dbinom{3}{1}+\dbinom{3}{2}+\dbinom{3}{3}=2^3. \]

The argument can easily be extended to prove the result for a set of \(n\) elements.

Observation 4

In any row of Pascal's triangle, the sum of the first, third, fifth, \(\dots\) numbers is equal to the sum of the second, fourth, sixth, \(\dots\) numbers.

To prove this observation, we use the binomial theorem in the form

\[ (1+x)^n = \dbinom{n}{0}+ \dbinom{n}{1}x + \dbinom{n}{2}x^2+\dots+\dbinom{n}{r}x^r+\dots+ \dbinom{n}{n-1}x^{n-1} + \dbinom{n}{n}x^n. \]

Let \(x=-1\). Then

\[ 0 = \dbinom{n}{0}- \dbinom{n}{1} + \dbinom{n}{2}-\dbinom{n}{3} + \dots+(-1)^{r}\dbinom{n}{r}+\dots+ (-1)^{n-1}\dbinom{n}{n-1} + (-1)^n\dbinom{n}{n}. \]

Therefore

\[ \dbinom{n}{0}+\dbinom{n}{2}+\dbinom{n}{4}+\cdots = \dbinom{n}{1}+\dbinom{n}{3}+\dbinom{n}{5}+\cdots, \]

which is the observation.

This shows that, for the expansion of \((1+x)^n\), the sum of the coefficients of the even powers is equal to the sum of the coefficients of the odd powers. Using Observation 3, it follows that each of these sums is equal to \(2^{n-1}\).

For example, for \(n=6\) we have

\[ \dbinom{6}{0}+ \dbinom{6}{2}+\dbinom{6}{4} +\dbinom{6}{6} = 2^5 = \dbinom{6}{1}+ \dbinom{6}{3}+\dbinom{6}{5}, \]

and for \(n=7\) we have

\[ \dbinom{7}{0}+ \dbinom{7}{2}+\dbinom{7}{4} +\dbinom{7}{6} = 2^6 = \dbinom{7}{1}+ \dbinom{7}{3}+\dbinom{7}{5} + \dbinom{7}{7}. \]

Next page - Content - Applying the binomial theorem