Beth lives in a house with thirteen stairs. She can go down the stairs one at a time or two at a time.
For example, she could go down 1 step, then 1 step, then 2 steps, then 2, 2, 1, 2, 1, 1.
In how many different ways can she go downstairs?
There are various ways of approaching this; we’ll describe one elegant argument here.
Let \(B_n\) denote the number of ways in which Beth can go down \(n\) stairs. We can find the values of \(B_n\) for some small values of \(n\).
If there is only one stair then Beth has only one possible way to go downstairs.
If there are two stairs, then Beth can go down in a big step, or two small steps: 2, or 1, 1.
If there are three stairs, then Beth’s options are 1, 2 or 1, 1, 1 or 2, 1.
If there are four stairs, then her options are 1, 1, 2 or 1, 1, 1, 1 or 1, 2, 1 or 2, 2 or 2, 1, 1.
Listing all the options is starting to become a bit tedious, and we have to be careful to make sure that we have included them all. That’s good, because it prompts us to look for what’s really going on, which might help us to generalise.
If there are five stairs, then Beth can take a small step or a big step to start with. If she starts with a small step, then she has four remaining stairs, so her options in this case are 1, 1, 1, 2 or 1, 1, 1, 1, 1 or 1, 1, 2, 1 or 1, 2, 2 or 1, 2, 1, 1. If she starts with a big step, then she has three remaining stairs, giving her the options 2, 1, 2 or 2, 1, 1, 1 or 2, 2, 1.
We can summarise the numbers we’ve found.
| \(n\) | \(B_n\) |
|---|---|
| \(1\) | \(1\) |
| \(2\) | \(2\) |
| \(3\) | \(3\) |
| \(4\) | \(5\) |
| \(5\) | \(8\) |
The numbers in the right-hand column might be familiar as the Fibonacci numbers, which is interesting, but at least as interesting is our observation above that \(B_5 = B_4 + B_3\). We can try to generalise that to help us.
When faced with \(n\) stairs, Beth can start by taking a small step or a big step. If she takes a small step, then she has \(n-1\) stairs remaining, which she can go down in any of \(B_{n-1}\) ways. If she takes a big step, then she has \(n-2\) stairs remaining, which she can go down in any of \(B_{n-2}\) ways. Every possible way of going down \(n\) stairs falls into exactly one of those two categories, so we see that \(B_n = B_{n-1} + B_{n-2}\) (when \(n \geq 3\)).
We can now use that recurrence relation to find \(B_{13}\) (which the question asked for). We have \[\begin{align*} B_6 &= B_5 + B_4 = 8 + 5 = 13 \\ B_7 &= B_6 + B_5 = 13 + 8 = 21 \\ B_8 &= B_7 + B_6 = 21 + 13 = 34 \\ B_9 &= B_8 + B_7 = 34 + 21 = 55 \\ B_{10} &= B_9 + B_8 = 55 + 34 = 89 \\ B_{11} &= B_{10} + B_9 = 89 + 55 = 144 \\ B_{12} &= B_{11} + B_{10} = 144 + 89 = 233 \\ B_{13} &= B_{12} + B_{11} = 233 + 144 = 377. \end{align*}\]These numbers really do look a lot like the Fibonacci numbers, so let’s convince ourselves that they are.
Define the Fibonacci numbers by \(F_0 = 0\), \(F_1 = 1\), and \(F_n = F_{n-1} + F_{n-2}\) for \(n \geq 2\).
We have already seen that \(B_1 = F_2\) and \(B_2 = F_3\). Now \(B_3 = B_2 + B_1 = F_3 + F_2 = F_4\), and \(B_4 = B_3 + B_2 = F_4 + F_3 = F_5\), and so on. So we see that \(B_n = F_{n+1}\) for all \(n \geq 1\).
This is essentially an example of an argument by mathematical induction. This is a way of making formal the “and so on” above.
We have shown that \(B_1 = F_2\) and \(B_2 = F_3\). If at any stage we know that \(B_{n-1} = F_n\) and \(B_{n-2} = F_{n-1}\), then we have \(B_n = B_{n-1} + B_{n-2} = F_n + F_{n-1} = F_{n+1}\). Those pieces of information combine, using the principle of mathematical induction, to tell us that \(B_n = F_{n+1}\) for all \(n \geq 1\).
Susie lives in the same house as Beth. Her legs are longer, so she can go down the stairs one at a time, or two at a time, or three at a time.
In how many different ways can she go downstairs?
Let \(S_n\) denote the number of ways in which Susie can go downstairs.
We can find the first few values of \(S_n\). We see that \(S_1 = B_1\) and \(S_2 = B_2\), because the ability to go down three stairs at a time is not much help when there are fewer than three stairs. But after that, Susie starts to have more options than Beth.
| \(n\) | \(B_n\) |
|---|---|
| \(1\) | \(1\) |
| \(2\) | \(2\) |
| \(3\) | \(4\) |
In how many ways can Susie go down four stairs? Rather than trying to list possibilities, we can try to use the same sort of thinking that we developed for counting Beth’s options.
To go down four stairs, Susie can start by taking a small step, a large step or a huge step. If she takes a small step, then she has \(S_3\) ways to go down the remaining three stairs. If she takes a large step, then she has \(S_2\) ways to go down the remaining two steps. And if she takes a huge step, then she has \(S_1\) ways to go down the remaining one step. So we see that \(S_4 = S_3 + S_2 + S_1 = 4 + 2 + 1 = 7\).
We can now generalise that to the case where Susie wants to go down \(n\) stairs (where \(n \geq 4\)). If she starts with a small step, then she has \(S_{n-1}\) ways left. If she starts with a large step, then she has \(S_{n-2}\) ways left. And if she starts with a huge step, then she has \(S_{n-3}\) ways left. So we see that \(S_n = S_{n-1} + S_{n-2} + S_{n-3}\).
We can now use this recurrence relation to find \(S_{13}\). We have \[\begin{align*} S_4 &= S_3 + S_2 + S_1 = 4 + 2 + 1 = 7 \\ S_5 &= S_4 + S_3 + S_2 = 7 + 4 + 2 = 13 \\ S_6 &= S_5 + S_4 + S_3 = 13 + 7 + 4 = 24 \\ S_7 &= S_6 + S_5 + S_4 = 24 + 13 + 7 = 44 \\ S_8 &= S_7 + S_6 + S_5 = 44 + 24 + 13 = 81 \\ S_9 &= S_8 + S_7 + S_6 = 81 + 44 + 24 = 149 \\ S_{10} &= S_9 + S_8 + S_7 = 149 + 81 + 44 = 274 \\ S_{11} &= S_{10} + S_9 + S_8 = 274 + 149 + 81 = 504 \\ S_{12} &= S_{11} + S_{10} + S_9 = 504 + 274 + 149 = 927 \\ S_{13} &= S_{12} + S_{11} + S_{10} = 927 + 504 + 274 = 1705. \end{align*}\]These numbers are sometimes known as the Tribonacci numbers, by analogy with Fibonacci!
What would happen if Beth and Susie move to another house with a different number of stairs?
We have found recurrence relations for each sequence, which we can use to help us find the answers for other sizes of house.
