Add new comment

It's a long way to the top: Solution

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 patter

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 $n$ steps. Can you find a formula to express the number of ways there of climbing $n$ steps using leaps of one and two?

Solution

Let’s write $S(n)$ for the number of ways to climb a flight of stairs with $n$ steps. There are two possibilities for starting my climb: I could start it using a single step or a leap of two steps. If it’s the former, then there are $n-1$ steps left to climb, which I can do in $S(n-1)$ ways. If it’s the latter, there are $n-2$ steps left to climb, which I can do in $S(n-2)$ ways. This means that

$S(n) = S(n-1) + S(n-2).$

This is a recurrence relation. If I know $S(1)$ and $S(2)$ then I can work out $S(3)$ , which I can then use to work out $S(4)$ , then $S(5)$ , etc.

Clearly $S(1) = 1.$ There is only one way I can climb up one step and that’s using, well, one step. It’s also easy to see that $S(2) = 2.$ I can climb up two steps using two single steps or one leap of two. This gives

$S(3) = S(2)+S(1) = 2+1 = 3,$

$S(4) = S(3)+S(2) = 3+2 = 5,$

$S(5) = S(4)+S(3) = 5+3 = 8,$

$S(6) = S(5)+S(4) = 8+5 = 13,$

and so on. This sequence of numbers might start to look familiar. It's the Fibonacci sequence, which happens to be defined via a recurrence relation in exactly the same way as we defined it here: each number is the sum of the two previous ones. (To be totally accurate, the Fibonacci sequence actually has the first two terms being equal to 1 and 1, rather than 1 and 2, so what we have here is the sequence displaced by a term.)

Carrying on with the calculations we see

$S(7) = S(6)+S(5) = 13+8 = 21,$