A staircase has 10 steps. Going up, you may take either 1 step or 2 steps at a time, in any mixture. In how many different ways can you climb the whole staircase?

The last move onto step n arrives either from step n − 1 or from step n − 2, so the number of ways to reach step n is the sum of the ways to reach the two steps below it. Starting with 1 way to reach step 1 and 2 ways to reach step 2, the counts run 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, so step 10 can be reached in 89 ways. The traps: 55 is the count for 9 steps and 144 the count for 11 steps, both from starting the chain one place out; 100 is the guess that ten steps with two choices each somehow gives a round hundred.