1 Step 2 Step
2 out of 3
Liam's house has a staircase with 12 steps. He can go down the steps one at a time or two at time. In how many different ways can Liam go down the 12 steps?
Problem
1 Step 2 Step printable worksheet
Liam's house has a staircase with 12 steps. He can go down the steps one at a time or two at a time.
For example, he could go down 1 step, then 1 step, then 2 steps, then 2, 2, 1, 1, 1, 1.
In how many different ways can Liam go down the 12 steps, taking one or two steps at a time?
Getting Started
Perhaps it might be a good idea to start with a simpler example.
Making careful lists, counting and looking for a pattern are useful strategies for exploring this problem.
Once you spot a pattern you should try to work out why the pattern occurs.
Student Solutions
This problem is a tricky one because it can be a bit tempting to try to count all the possibilities one by one. While this is sometimes necessary, often there's a better approach.
Tayla, Cindy and Iris from Elm Park School started with smaller flights of stairs and spotted a pattern. Miss Hodgetts' Y9 Class from Ounsdale High School and many other people also saw the pattern. Well done.
Suppose Liam is going down $12$ steps. He can start by taking one step, then he has $11$ more steps to go down. The only other possibility is that he starts by taking two steps and has $10$ more steps to go down. So how does the number of ways of going down $12$ steps depend on the number of ways of going down $10$ steps and $11$ steps?
It helped to start with small numbers of steps and many people sent in lists like this one:
| 1 Step | 1 | Total 1 way |
| 2 Steps | 1,1 or 2 | Total 2 ways |
| 3 Steps | 1,1,1 or 1,2 or 2,1 | Total 3 ways |
| 4 Steps | 1,1,1,1 or 1,1,2 or 1,2,1 or 2,1,1 or 2,2 | Total 5 ways |
| 5 Steps | 1,1,1,1,1 or 1,1,1,2 or 1,1,2,1 or 1,2,1,1 or 1,2,2 or 2,2,1 or 2,1,2 or 2,1,1,1 | Total 8 ways |
| 6 Steps | 1,1,1,1,1,1 or 1,1,1,1,2 or 1,1,1,2,1 or 1,1,2,1,1 or 1,2,1,1,1 or 1,1,2,2 or 1,2,2,1 or 2,1,1,2 or 2,1,2,1 or 2,2,1,1 or 2,2,2 or 2,1,1,1,1 or 1,2,1,2 | Total 13 ways |
| etc. |
The tricky pattern to spot is that each total on the right is the sum of the previous two totals.
Peter pointed out that this can be expressed simply as an algebraic relation. He used the notation $S_n$ to mean the total number of ways of descending $n$ steps.
Then the formula is
$S_n = S_{n-1} + S_{n-2}$
So, since $S_1=1$ and $S_2=2$, that means $S_3=3$, $S_4=5$, $S_5=8$, $S_6=13$, $S_7=21$, $S_8=34$, $S_9=55$, $S_{10}=89$, $S_{11}=144$, and $S_{12}=233$.
The number of ways to get to the 12th step is 233.
The reason for this pattern is very simple. For the first step Liam has two choices:
i) Jump down 1 step. This leaves n-1 steps.
ii) Jump down 2 steps. This leaves n-2 steps.
So if you know that Liam has $S_{n-1}$ ways of going down n-1 steps, and also $S_{n-2}$ ways of going down n-2 steps, all of these, when combined with the right choice of first step, give a way of going down n steps. This sum is exactly the relation $S_n = S_{n-1} + S_{n-2}$.
Congratulations to everyone who managed to spot this pattern and find this answer. Those of you who have heard of the Fibonacci numbers will notice that the totals are the Fibonacci sequence, starting at 1, 2, ...
In fact there is a formula for finding any Fibonnaci number without having to add up all the previous ones. You might like to try and find out what it is. This would make counting the total number of ways of jumping down 1000000 steps much easier, but you'll probably never need to jump down that many steps.
Another interesting detail is that there are many number sequences that follow the pattern $S_n = S_{n-1} + S_{n-2}$. The Lucas numbers are an example. Can you see that if you specify the first two numbers, all the rest of the sequence is given without any more choice? What about if you are told only the first number, how many possible sequences with this addition property are there?
There is another reasonably quick and easy way to find the answer 233 if you're confident with combinations and binomial coefficients. These are some stage 5 topics that you can read about in this article. Matias sent in his idea:
First of all I broke down all the different ways of down 12 stairs:
- Always jump one step at a time
- Jump two steps 1 time, and one step 10 times
- Jump two steps 2 times, and one step 8 times
- Jump two steps 3 times, and one step 6 times
- Jump two steps 4 times, and one step 4 times
- Jump two steps 5 times, and one step 2 times
- Always jump two steps at a time
Matias then used binomial coefficients. These strange and useful numbers have a special notation and formula, explained in more detail in the article.
$n \choose r$ means 'the number of ways of choosing $r$ objects from a total of $n$' where the order of the choices doesn't matter. It's said 'n choose r'
For example ${4 \choose 2} = 6$ because from the numbers 1, 2, 3, 4 I can make six pairs:
12, 13, 14, 23, 24, 34 (remember we consider 34 the same as 43)
The formula for the binomial coefficients uses the factorial notation $n! = n\times(n-1)\times(n-2)\times...\times 2 \times 1$ and is
$${n \choose r} = \frac{n!}{r!(n-r)!}$$
So the factorials on the right give a formula for 'n choose r'.
This can be linked to jumping down stairs because Liam can decide where to put his two-step jumps. If there are n total jumps, and exactly r of them are two-step, then there are $n \choose r$ possible ways of making the jumps. We have to 'choose' r different places out of the n steps to put the double jumps.
For the item 1 there's 1 possibility
For the item 2 there are 11 possibilities because this is 11 choose 1
For the item 3 there are 45 possibilities because this is 10 choose 2
For the item 4 there are 84 possibilities because this is 9 choose 3
For the item 5 there are 70 possibilities because this is 8 choose 4
For the item 6 there are 21 possibilities because this is 7 choose 5
For the item 7 there are 1 possibility
Total of the possibilities will be: 1+11+45+84+70+21+1 = 233
Final result = 233 possibilities.
Brilliant work everyone. This was a problem which can involve some sophisticated and difficult maths!
Teachers' Resources
Using NRICH Tasks Richly describes ways in which teachers and learners can work with NRICH tasks in the classroom.
Why do this problem?
This problem offers a great opportunity to demonstrate to students the importance of working systematically and using earlier results to explain what is happening and hence calculate later results.
Possible approach
The Article Go Forth and Generalise may be of interest.
Start by posing the problem:
"Liam's house has a staircase with 12 steps. He can go down the steps one at a time or two at a time. For example: He could go down 1 step, then 1 step, then 2 steps, then 2, 2, 1, 1, 1, 1.
In how many different ways do you think Liam can go down the 12 steps, taking one or two steps at a time?"
You could invite students to suggest a number they know is going to be too small, and one they know is going to be too big, to establish a lower and upper bound for the problem. Give students a chance to express their thoughts about the task - they may make comments like:
"There are going to be loads of different ways"
"How are we going to be able to make sure we don't miss any?"
If no-one has suggested it: "Perhaps we could work on a simpler version of the problem to see if that helps? Let's see how many ways there are of going down three, four, five or six steps."
Students could all work on these or they could be shared out with different groups working on different sizes of staircase.
Then bring the class together and invite students out to the board to list the number of different ways they found, while the rest of the class make sure they have worked in a way that makes sure they haven't missed any.
Once the number of ways for three, four, five and six steps have been worked out:
"With your partner, look at the number of ways for each different size of staircase, and see if you notice any patterns. In a short while we will return to the original problem of a staircase with twelve steps. Can you use what we have found out about smaller staircases to make predictions about the answer for twelve steps? Or any number of steps?"
Give students some time to work with their partner, and circulate, listening in for any who make connections. If they are struggling to make progress, here are some prompts you could use:
"How does the number of ways of descending 5 steps compare to the number of ways of descending 3 and 4 steps? What about the number of ways of descending 6 steps compared to the number of ways of descending 4 and 5 steps?"
"If I want to go down 5 steps and I start with a one-step, how many ways can I descend the remaining four steps?"
"If I want to go down 5 steps and I start with a two-step, how many ways can I descend the remaining three steps?"
Finally, bring the class together and discuss their findings.
Key questions
What is making it difficult?
"There'll be too many", "I can't keep track", "I might have done some twice"
Possible responses:-
"Work it out for fewer steps", "Try to find a logical way to order the options", "Work together and check each other's work".
Possible support
Another problem that uses a similar idea is Colour Building
Possible extension
What if I could also go down 3 steps at a time? Or 4 steps?
What if I could only go down 2 or 3 steps at a time (but not 1 step)?