How many ways up the stairs?
Tonight's idea
You climb a staircase taking one stair or two with each stride. In how many different ways can you get to the top? Order matters: a single then a double is a different climb from a double then a single.
Small cases first. One stair: 1 way. Two stairs: \(1 + 1\) or \(2\), so 2 ways. Three stairs: \(1 + 1 + 1\), \(1 + 2\), \(2 + 1\), so 3 ways. Listing ten stairs this way is hopeless. Look for a rule.
Think about the last stride. If it was a single, you were standing on stair \(n - 1\), and you could have reached that in any of the ways up \(n - 1\) stairs. If it was a double, you were on stair \(n - 2\). Every climb ends one way or the other, never both. Write \(W(n)\) for the number of ways up \(n\) stairs.
\(W(n) = W(n-1) + W(n-2)\)
Each count is the sum of the two before it: 1, 2, 3, 5, 8, … These are the Fibonacci numbers.
Watch one: ten stairs
Start from \(W(1) = 1\) and \(W(2) = 2\). Keep adding the last two.
| Stairs \(n\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Ways \(W(n)\) | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
There are 89 ways up ten stairs, and no list was needed. \(89 = 55 + 34\): the 55 climbs that end with a single from stair 9, and the 34 that end with a double from stair 8.
The rule only works because the two groups do not overlap and nothing is left out. Check it against the figure: \(W(4) = 3 + 2 = 5\).
Your turn
- List every way up 5 stairs. How many end with a single, and how many with a double?
- Carry the table on. (a) How many ways are there up 12 stairs? (b) Which is the shortest staircase with more than 1,000 ways up?
- Now a stride may cover 1, 2 or 3 stairs. (a) Explain why each count is the sum of the three before it. (b) The counts start 1, 2, 4. How many ways are there up ten stairs?
- Back to singles and doubles. Stair 5 of a ten-stair staircase has wet paint, and you must not tread on it. How many ways up are there now?
Stretch: count the doubles
A climb of ten stairs with three doubles has four singles: seven strides. Choose which three are the doubles: \(\dbinom{7}{3} = \dfrac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35\) ways. Count the climbs with 0, 1, 2, 4 and 5 doubles the same way. What should the six counts add up to? Check.
Answers
- \(1{+}1{+}1{+}1{+}1\), \(2{+}1{+}1{+}1\), \(1{+}2{+}1{+}1\), \(1{+}1{+}2{+}1\), \(2{+}2{+}1\) end with a single: 5 ways, one for each way up 4 stairs. \(1{+}1{+}1{+}2\), \(2{+}1{+}2\), \(1{+}2{+}2\) end with a double: 3 ways, one for each way up 3 stairs. Total \(5 + 3 = 8\).
- (a) \(W(11) = 144\) and \(W(12) = 233\). (b) The counts go on 377, 610, 987, 1,597, so 16 stairs is the first with more than 1,000 ways.
- (a) The last stride covered 1, 2 or 3 stairs, so just before it you stood on stair \(n-1\), \(n-2\) or \(n-3\). The three groups do not overlap and cover every climb. (b) 1, 2, 4, 7, 13, 24, 44, 81, 149, 274. There are 274 ways.
- To miss stair 5 you must stand on stair 4 and take a double to stair 6. There are \(W(4) = 5\) ways to reach stair 4. From stair 6 there are 4 stairs left, another \(W(4) = 5\) ways. Each start can go with each finish: \(5 \times 5 = 25\) ways. Check from the other side: climbs that do use stair 5 number \(W(5) \times W(5) = 64\), and \(89 - 64 = 25\).
Stretch. With \(k\) doubles there are \(10 - 2k\) singles, so \(10 - k\) strides, and \(\dbinom{10-k}{k}\) climbs. That gives \(\dbinom{10}{0} = 1\), \(\dbinom{9}{1} = 9\), \(\dbinom{8}{2} = 28\), \(\dbinom{7}{3} = 35\), \(\dbinom{6}{4} = 15\), \(\dbinom{5}{5} = 1\). Every climb has some number of doubles, so they must add to \(W(10)\): \(1 + 9 + 28 + 35 + 15 + 1 = 89\). These six numbers lie along a slanting line through Pascal's triangle.