Counting Steps
When climbing steps, some people like to take the steps two at a time, at least part of the time. That leads to the general question of how many different ways there are of going up steps this way.
THE CHALLENGE
How many different ways are there of going up 10 steps where you are making some combination of single and double steps along the way (it may be all single steps or all double steps or some mixture)? How about 20 steps?
EXPLORATION
Do you see a pattern you recognize? Can you find a shortcut that will make it easier to count all the ways of doing this?
Notes
THE CHALLENGE & EXPLORATION
This is another visit with Fibonacci Numbers. The first few counts of how many ways there are of doing this are: 1, 2, 3, 5, and 8. After doing the bee ancestry puzzle, and then seeing the first few numbers for this one, your students should be suspicious.
The tricky part is seeing where the Fibonacci rule comes into play. Let’s look at going up ten steps as an example. You can divide the ways of doing ten steps into two buckets. In the first one is all the ways of going up nine steps and then taking a single step to get to the tenth. The other one is all the ways of going up eight steps and then take a double step to get to the tenth. Every possibility is counted this way, and nothing is counted twice.
In general, the number of ways of going up n steps will be the number of ways of going up (n – 1) steps plus the number of ways of going up (n – 2) steps. That is exactly the Fibonacci rule.