Every time I come home I have to climb a flight of stairs. When I'm feeling energetic I sometimes take two steps at a time. This gives me a number of ways to climb the stairs. For example, if there are ten steps, I could climb them taking five leaps of two, giving the pattern
2, 2, 2, 2, 2.
Or I could only use a leap of two at the beginning and the end, giving the pattern
2, 1, 1, 1, 1, 1, 1, 2.
How many ways are there all together of climbing the ten steps?
Being a mathematician, I don’t have ten steps of course, but I have steps. Can you find a formula to express the number of ways there are of climbing steps using leaps of one and two?
Hint: Think recurrently! I could start my climb with a leap of one or two...