C. Discrete Functions · Sequences and Series

Pascal's Triangle: A Recursive Pattern

C1.5About 70 minutes

Learning goals

I can build Pascal's triangle recursively and write its recursion formula.
I can find and describe patterns in Pascal's triangle (symmetry, row sums, diagonals, Fibonacci numbers).
I can use Pascal's triangle to count routes on a grid.

Words to know

Pascal's triangle
A triangular array of numbers with 1s along the edges, where each inside number is the sum of the two numbers just above it.

row n
In this unit the top row (just a 1) is row 0, the next is row 1, and so on. Row n has n + 1 entries.

tₙ,ᵣ
The entry in row n, position r, where positions also start at 0. For example, t₄,₂ = 6.

diagonal
A line of entries running parallel to an edge of the triangle, such as 1, 2, 3, 4, … or 1, 3, 6, 10, …

A triangle that builds itself

Start with a 1 at the top. Put 1s down both edges. Then fill in every inside spot with the sum of the two numbers directly above it. That is all. Yet the triangle you get hides the natural numbers, the triangular numbers, powers of 2, the Fibonacci numbers, and (in the next lesson) the shortcut for expanding expressions like (x + 2)⁵.

It is called Pascal's triangle after the French mathematician Blaise Pascal, who wrote about it in the 1600s. Mathematicians in Persia, India and China knew it centuries earlier; in China it is called Yang Hui's triangle, after a mathematician of the 1200s.

Rows 0 to 7 of Pascal's triangle. The highlighted diagonals hold the natural numbers, the triangular numbers and the tetrahedral numbers.

The recursion formula

We number the rows from 0 at the top, and the positions in each row from 0 on the left. Then tₙ,ᵣ is the entry in row n, position r. For example, row 4 is 1, 4, 6, 4, 1, so t₄,₀ = 1, t₄,₁ = 4 and t₄,₂ = 6.

The two numbers above tₙ,ᵣ are tₙ₋₁,ᵣ₋₁ (up and to the left) and tₙ₋₁,ᵣ (up and to the right). So Pascal's triangle follows the recursion formula

tₙ,ᵣ = tₙ₋₁,ᵣ₋₁ + tₙ₋₁,ᵣ, with tₙ,₀ = tₙ,ₙ = 1.

Like every recursion, it needs a starting point (the 1s on the edges) and a rule (add the two above).

Worked example

Example 1: Building the next row

Row 7 is 1, 7, 21, 35, 35, 21, 7, 1. Write row 8.

Start and end with 1.
Add neighbouring pairs from row 7: 1 + 7 = 8, 7 + 21 = 28, 21 + 35 = 56, 35 + 35 = 70, 35 + 21 = 56, 21 + 7 = 28, 7 + 1 = 8.
Row 8 has 9 entries (n + 1 = 9) ✓.

1, 8, 28, 56, 70, 56, 28, 8, 1

Worked example

Example 2: Using the notation

Use row 8 to find t₉,₄ and t₉,₅.

t₉,₄ = t₈,₃ + t₈,₄ = 56 + 70 = 126
t₉,₅ = t₈,₄ + t₈,₅ = 70 + 56 = 126
They are equal because the triangle is symmetric: t₉,₄ and t₉,₅ are the same distance from the two ends of row 9.

t₉,₄ = t₉,₅ = 126

Patterns to investigate

Symmetry: each row reads the same forwards and backwards: tₙ,ᵣ = tₙ,ₙ₋ᵣ.
Row sums: 1, 2, 4, 8, 16, 32, …. The sum of row n is 2ⁿ. Each entry is used twice to make the next row, so each row sum is double the one before.
Diagonals: the first diagonal is all 1s; the second is the natural numbers 1, 2, 3, 4, …; the third is the triangular numbers 1, 3, 6, 10, 15, …; the fourth is the tetrahedral numbers 1, 4, 10, 20, 35, … (the numbers of balls in triangular pyramids).
Hockey stick: add entries down a diagonal, starting from a 1; the total is the entry just below the last one, on the other side. For example, 1 + 3 + 6 + 10 = 20.
Shallow diagonals: add the entries along "shallow" diagonals and you get the Fibonacci numbers 1, 1, 2, 3, 5, 8, 13, ….
Powers of 11: rows 0 to 4 read as numbers are 1, 11, 121, 1331, 14641 = 11⁰, 11¹, 11², 11³, 11⁴.
Prime rows: in row 5 (5, 10, 10, 5) and row 7 (7, 21, 35, 35, 21, 7), every entry except the 1s is a multiple of the row number. This happens in every row whose number is prime.

Left: the hockey stick pattern. The highlighted diagonal 1 + 3 + 6 + 10 adds up to the entry 20 just below and to the side. Right: adding along a shallow diagonal gives a Fibonacci number.

Worked example

Example 3: Using patterns

(a) What is the sum of the entries in row 10? (b) Use the hockey stick to find 1 + 4 + 10 + 20 + 35. (c) What is the sum of the shallow diagonal 1 + 6 + 10 + 4?

(a) The sum of row n is 2ⁿ, so row 10 sums to 2¹⁰ = 1024.
(b) 1, 4, 10, 20, 35 run down the fourth diagonal, ending at t₇,₃ = 35. The hockey stick ends at the entry below it on the other side: t₈,₄ = 70. Check: 1 + 4 + 10 + 20 + 35 = 70 ✓.
(c) 1 + 6 + 10 + 4 = 21, a Fibonacci number (t₈ of the Fibonacci sequence).

(a) 1024 (b) 70 (c) 21

Counting routes

Pascal's triangle also counts paths. Suppose you walk from home to school on a grid of streets and only ever go east or south (so every route is as short as possible). The number of routes to a corner is the number of routes to the corner just north of it plus the number to the corner just west of it, because you must arrive from one of those two. That is the same "add the two before" rule, so the counts are the entries of Pascal's triangle, tilted on its side.

Counting shortest routes on a 4-by-3 grid of blocks. The numbers at the corners are entries of Pascal's triangle; the school corner is t₇,₃ = 35.

Worked example

Example 4: Routes to school

Ava's school is 4 blocks east and 3 blocks south of her home. How many shortest routes are there?

Label the home corner 1. Every corner along the top edge and the left edge has only 1 route (straight along the edge).
Fill in each other corner with (number above) + (number to the left), as in the diagram: second row 1, 2, 3, 4, 5; third row 1, 3, 6, 10, 15; fourth row 1, 4, 10, 20, 35.
Any route uses 4 + 3 = 7 blocks, and the answer 35 is t₇,₃ in row 7 of Pascal's triangle.

35 shortest routes

Just for fun

Pascal's triangle has excellent manners.

Every single number in it gives full credit to the two numbers above it.

Hands-on activity

Colour the odd numbers

You need: a sheet of paper (grid paper helps), a pencil and two coloured pencils or markers.

Write rows 0 to 15 of Pascal's triangle. Use the recursive rule: add the two numbers above. (The numbers get big; row 15 has 6435 in the middle. You only need to know whether each number is odd or even, so you can use odd + odd = even, odd + even = odd, even + even = even instead of adding.)
Shade every odd entry in one colour and every even entry in the other.
Describe the picture.
Check one pattern from the lesson on your rows: is row 15's sum 2¹⁵ = 32 768? (You can add with a calculator if you wrote the full numbers.)

What to look for: the odd entries form triangles inside triangles, a shape known as the Sierpinski triangle. Rows 1, 3, 7 and 15 are all odd. Row 15 is 1, 15, 105, 455, 1365, 3003, 5005, 6435, 6435, 5005, 3003, 1365, 455, 105, 15, 1, which does sum to 32 768.

Your turn

Write rows 0 to 6 of Pascal's triangle.

Find t₆,₂ and t₆,₄.

Write the recursion formula for Pascal's triangle and use it to find t₁₀,₃ given t₉,₂ = 36 and t₉,₃ = 84.

What is the sum of the entries in row 7? In row 12?

Which diagonal holds the triangular numbers? What is the 6th triangular number?

How many shortest routes go from one corner of a 3-by-2 grid of blocks to the opposite corner?

More practice: warm-up

How many entries are in row 9?

What is t₈,₁?

Row 5 is 1, 5, 10, 10, 5, 1. What is row 6?

What number is at both ends of every row?

What is the sum of row 3?

More practice: on your own

Use the hockey stick pattern to find 1 + 2 + 3 + 4 + 5 + 6 + 7.

Find the sum of the shallow diagonal that starts at t₇,₀: 1 + 6 + 10 + 4.

Row 11 starts 1, 11, 55, 165, 330, 462, …. Complete it using symmetry and check the sum.

Is every entry in row 11 (except the 1s) a multiple of 11? Check three of them.

How many shortest routes are there from one corner of a 5-by-5 grid of blocks to the opposite corner?

Challenge

Explain why the sum of row n + 1 is double the sum of row n.

Find the alternating sum of row 6: 1 − 6 + 15 − 20 + 15 − 6 + 1. Try another row. Make a conjecture.

A city has a park blocking one corner of the grid in Example 4: the corner 2 blocks east and 1 block south of Ava's home cannot be used. How many shortest routes to school remain?

Check your understanding

Quiz

Which is row 5 of Pascal's triangle?

What is the sum of the entries in row 9?

Which recursion formula describes Pascal's triangle?

The third diagonal (1, 3, 6, 10, …) contains which numbers?

Adding along the shallow diagonals of Pascal's triangle gives:

How many shortest routes go 2 blocks east and 2 blocks south?

For parents and teachers

Big idea: Expectation C1.5 includes investigating recursive patterns in Pascal's triangle and representing them in different ways. The triangle is itself a recursion: each entry comes from the two above it. The next lesson uses it to expand binomials (C1.6).

How to help: Have your teen build the triangle from memory to row 8, then ask them to show you three patterns. The colouring activity is a good one to do together.

Common difficulties:

Off-by-one errors with row and position numbers. The top row is row 0, and the first entry in each row is position 0. (Some textbooks number from 1; check which convention a resource uses.)
Adding the wrong pair when building a row. Every inside entry comes from the two directly above it.
Route problems where moves can go backwards. Pascal's triangle only counts the shortest routes (only east or south, for example).