Or search by topic
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.
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.
What is making it difficult?
"There'll be too many", "I can't keep track", "I might have done some twice"
"Work it out for fewer steps", "Try to find a logical way to order the options", "Work together and check each other's work".
Another problem that uses a similar idea is Colour Building
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)?
The well known Fibonacci sequence is 1 ,1, 2, 3, 5, 8, 13, 21.... How many Fibonacci sequences can you find containing the number 196 as one of the terms?
How many different ways can I lay 10 paving slabs, each 2 foot by 1 foot, to make a path 2 foot wide and 10 foot long from my back door into my garden, without cutting any of the paving slabs?
Here are some circle bugs to try to replicate with some elegant programming, plus some sequences generated elegantly in LOGO.