Skip to content

Patterns in Pascal's triangle

Counting and combinations · level 7, lesson 4 of 6

A question to start

Colour every odd number in the first 32 rows of Pascal's triangle and leave the even ones blank. You might expect a random scatter of dots. Instead you get this:

A triangle made of three smaller triangles, each made of three smaller ones, with a hole in the middle of each. It is called the Sierpinski triangle, after the Polish mathematician Wacław Sierpiński, who studied it in 1915. Why does a triangle built by adding numbers draw a picture like this? By the end of the lesson you will be able to prove it, and you will have found several other famous sequences hiding in the same triangle.

The idea

The rule that builds everything

Every pattern in this lesson comes from one rule, Pascal's rule from level 5: each entry is the sum of the two entries just above it,

\[\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.\]

The counting reason was: to choose \(k\) people from \(n\), look at one particular person; either they are on the team (choose the other \(k - 1\) from the remaining \(n - 1\)) or they are not (choose all \(k\) from the remaining \(n - 1\)). Below, each pattern gets a proof from this rule, and where possible a counting reason too.

The diagonals: counting numbers, triangular numbers, and more

Read the triangle along its slanting lines (from the edge inwards):

  • Diagonal 0 is all 1s: \(\dbinom{n}{0} = 1\).
  • Diagonal 1 is \(1, 2, 3, 4, \ldots\): \(\dbinom{n}{1} = n\).
  • Diagonal 2 is \(1, 3, 6, 10, 15, \ldots\): the triangular numbers, \(\dbinom{n}{2} = \dfrac{n(n-1)}{2}\), which also count the handshakes among \(n\) people (level 1) because a handshake is a choice of 2 people.
  • Diagonal 3 is \(1, 4, 10, 20, 35, \ldots\): the tetrahedral numbers, the numbers of oranges in a triangular pyramid stack: 1 on top, then 3 below it, then 6, and so on.

The hockey-stick identity

Run down a diagonal from its first entry and add: \(1 + 3 + 6 + 10 = 20\). The total sits just below the last entry, one step off the diagonal. The shape, a long straight handle and a short blade, gives the identity its name.

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 + 3 + 6 + 10 = 20

Hockey-stick identity. For whole numbers \(0 \le r \le n\),

\[\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}.\]

Proof from Pascal's rule. Start from the answer and unpick it. By Pascal's rule, \(\dbinom{n+1}{r+1} = \dbinom{n}{r} + \dbinom{n}{r+1}\). Split the last part again: \(\dbinom{n}{r+1} = \dbinom{n-1}{r} + \dbinom{n-1}{r+1}\). Keep going. Each split peels off one more entry of diagonal \(r\), moving up, until what is left is \(\dbinom{r+1}{r+1} = 1 = \dbinom{r}{r}\). Adding all the pieces gives the identity. In the picture: \(20 = 10 + 10\), then \(10 = 6 + 4\), then \(4 = 3 + 1\).

Counting proof. Count the ways to choose \(r + 1\) numbers from \(\{1, 2, \ldots, n + 1\}\): the right side. Now sort the choices by their largest number. If the largest is \(m + 1\), the other \(r\) numbers must come from \(\{1, \ldots, m\}\), in \(\dbinom{m}{r}\) ways. The largest can be anything from \(r + 1\) up to \(n + 1\), so \(m\) runs from \(r\) to \(n\), and the piles have sizes \(\dbinom{r}{r}, \dbinom{r+1}{r}, \ldots, \dbinom{n}{r}\). Every choice is in exactly one pile, so the piles add to the total. ∎

With \(r = 1\) this is the old Gauss sum: \(1 + 2 + \cdots + n = \dbinom{n+1}{2}\). With \(r = 2\) it says that adding up triangular numbers gives tetrahedral numbers, which is how an orange pyramid is built, one triangular layer at a time.

Fibonacci on the shallow diagonals

Push the triangle against the left wall and add along lines that go up one row for every step right (the "shallow" diagonals). The sums are \(1, 1, 2, 3, 5, 8, 13, 21, \ldots\), the Fibonacci numbers, where each number is the sum of the two before it.

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 diagonal 0: 1 diagonal 1: 1 diagonal 2: 2 diagonal 3: 3 diagonal 4: 5 diagonal 5: 8 diagonal 6: 13 diagonal 7: 21

The shallow diagonal number \(d\) holds the entries \(\dbinom{d}{0}, \dbinom{d-1}{1}, \dbinom{d-2}{2}, \ldots\), so its sum is

\[S_d = \sum_{k \ge 0}\binom{d-k}{k}.\]

Counting reason. In how many ways can you climb a staircase of \(d\) steps, taking 1 or 2 steps at a time? A climb with \(k\) double-steps has \(d - 2k\) single steps, so \(d - k\) moves in all, and it is decided by which \(k\) of those \(d - k\) moves are doubles: \(\dbinom{d-k}{k}\) ways. So \(S_d\) counts all climbs of \(d\) steps. And the climbs obey the Fibonacci rule: the first move is a single (then \(d - 1\) steps remain) or a double (then \(d - 2\) remain), so \(S_d = S_{d-1} + S_{d-2}\). With \(S_0 = 1\) and \(S_1 = 1\) the sequence is \(1, 1, 2, 3, 5, 8, \ldots\). Level 8 builds whole lessons on recursions like this one.

Odd and even: the Sierpinski triangle explained

To know whether an entry is odd, you only need to know whether the two above it are odd: odd + even = odd, odd + odd = even, even + even = even. So the odd-even pattern obeys its own small Pascal rule, and you can draw it without working out any big numbers.

The key is a fact about rows whose number is a power of 2. Work with remainders on division by 2. Then \((1 + x)^2 = 1 + 2x + x^2\) has an even middle coefficient, so it behaves like \(1 + x^2\). Squaring again, \((1 + x)^4\) behaves like \((1 + x^2)^2\), so like \(1 + x^4\), and so on: \((1 + x)^{2^m}\) behaves like \(1 + x^{2^m}\). In words, row \(2^m\) is odd at its two ends and even everywhere in between. Row 4 is 1, 4, 6, 4, 1 and row 8 is 1, 8, 28, 56, 70, 56, 28, 8, 1. ✓

Now watch the pattern grow. Rows \(0\) to \(2^m - 1\) form some triangle \(T\). Row \(2^m\) is "odd, then a run of evens, then odd". The rows below it are built only from that row by the odd-even rule, and each odd end starts its own fresh copy of the top of the triangle, while the evens in between create nothing. So rows \(2^m\) to \(2^{m+1} - 1\) are two copies of \(T\) side by side, with an all-even gap between them. Three copies of \(T\) (one on top, two below) make the next triangle, and that is exactly how the Sierpinski triangle is built.

A neat consequence: the number of odd entries in row \(n\) is always a power of 2. Row 10 is 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, with 4 odd entries. (A theorem of Édouard Lucas from 1878 gives the exact rule: write \(n\) in base 2 and count its 1s; if there are \(s\) of them, row \(n\) has \(2^s\) odd entries. Ten is 1010 in base 2, with two 1s, and \(2^2 = 4\).)

A row whose number is prime

Row 7 is 1, 7, 21, 35, 35, 21, 7, 1: every entry except the 1s is a multiple of 7. This happens in every prime row. In \(\dbinom{p}{k} = \dfrac{p!}{k!\,(p-k)!}\) with \(0 < k < p\), the prime \(p\) divides the top, but every number in \(k!\) and \((p - k)!\) is smaller than \(p\), so none of them can cancel it. Row 11 (1, 11, 55, 165, 330, 462, ...) agrees. Row 6 is not prime, and \(\dbinom{6}{2} = 15\) is not a multiple of 6.

Worked examples

1. A Gauss sum by hockey stick. \(1 + 2 + \cdots + 10\) is diagonal 1 from \(\dbinom{1}{1}\) to \(\dbinom{10}{1}\), so it equals \(\dbinom{11}{2} = 55\).

2. Adding triangular numbers. \(1 + 3 + 6 + 10 + 15 + 21\) is diagonal 2 from \(\dbinom{2}{2}\) to \(\dbinom{7}{2}\), so it equals \(\dbinom{8}{3} = 56\). Check: \(1 + 3 + 6 + 10 + 15 + 21 = 56\). ✓

3. A shallow diagonal. \(\dbinom{7}{0} + \dbinom{6}{1} + \dbinom{5}{2} + \dbinom{4}{3} = 1 + 6 + 10 + 4 = 21\), the Fibonacci number after 13. It counts the climbs of a 7-step staircase.

4. Parity of a whole row. Which entries of row 16 are odd? Sixteen is \(2^4\), so only the two 1s at the ends. Row 15 is the last row of the 16-row triangle, so it is all odd: 16 odd entries, and indeed 15 is 1111 in base 2, with four 1s, and \(2^4 = 16\).

5. A product sum. Find \(1 \cdot 2 + 2 \cdot 3 + \cdots + 9 \cdot 10\). Each term \(k(k + 1) = 2\dbinom{k+1}{2}\), so the sum is \(2\left[\dbinom{2}{2} + \dbinom{3}{2} + \cdots + \dbinom{10}{2}\right] = 2\dbinom{11}{3} = 2 \times 165 = 330\).

Try it

  1. Use the hockey stick to find \(1 + 2 + 3 + \cdots + 20\).
  2. Find \(\dbinom{3}{3} + \dbinom{4}{3} + \dbinom{5}{3} + \dbinom{6}{3} + \dbinom{7}{3}\) in one step, then check by adding.
  3. Find \(\dbinom{9}{0} + \dbinom{8}{1} + \dbinom{7}{2} + \dbinom{6}{3} + \dbinom{5}{4}\). Which Fibonacci number is it?
  4. How many entries of row 10 are odd? Check by writing out the row.
  5. Which rows of Pascal's triangle have every entry odd? Explain using the Sierpinski picture.
  6. In how many ways can you climb 6 steps, 1 or 2 at a time? Find it from a shallow diagonal.
  7. Oranges are stacked in a triangular pyramid with 8 layers (1 on top, 3 in the next layer, 6, ...). How many oranges are there?
  8. Without working out row 13, explain why \(\dbinom{13}{5}\) is a multiple of 13.
Answers
  1. \(\binom{21}{2} = \frac{21 \times 20}{2} = 210\).
  2. \(\binom{8}{4} = 70\). Check: \(1 + 4 + 10 + 20 + 35 = 70\). ✓
  3. \(1 + 8 + 21 + 20 + 5 = 55\), the tenth Fibonacci number (1, 1, 2, 3, 5, 8, 13, 21, 34, 55).
  4. Row 10: 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1. The odd ones are 1, 45, 45, 1: 4. Ten is 1010 in base 2, two 1s, \(2^2 = 4\). ✓
  5. Rows \(1, 3, 7, 15, 31, \ldots\), that is \(n = 2^m - 1\) (and row 0). These are the bottom rows of the complete triangles in the Sierpinski picture, the last row before a row \(2^m\) that is even inside. In base 2 they are all 1s.
  6. \(\binom{6}{0} + \binom{5}{1} + \binom{4}{2} + \binom{3}{3} = 1 + 5 + 6 + 1 = 13\).
  7. The layers are the triangular numbers \(\binom{2}{2}, \ldots, \binom{9}{2}\), so the total is \(\binom{10}{3} = 120\). Check: \(1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 = 120\). ✓
  8. \(\binom{13}{5} = \frac{13!}{5!\,8!}\). The prime 13 divides \(13!\), but \(5!\) and \(8!\) are products of numbers less than 13, and no product of smaller numbers has the prime 13 as a factor. So the 13 does not cancel. (In fact \(\binom{13}{5} = 1287 = 13 \times 99\).)

Common mistake

Putting the hockey-stick total in the wrong place. The sum of a diagonal run sits one row below the last entry and one step inwards, on the next diagonal: \(\dbinom{n+1}{r+1}\), not \(\dbinom{n+1}{r}\). Check with a tiny case: \(1 + 2 + 3 = 6 = \dbinom{4}{2}\), and \(\dbinom{4}{1}\) would be 4.

Starting the run in the middle. The identity needs the run to start at the very first entry of the diagonal, \(\dbinom{r}{r} = 1\). A run like \(6 + 10 + 15\) is the difference of two hockey sticks: \(\dbinom{7}{3} - \dbinom{4}{3} = 35 - 4 = 31\).

Where it leads