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 \emph{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.)

*See this article to find out more about the Fibonacci sequence.*

## The way I look at this is,

The way I look at this is, the last step taken need not be considered because it is common to every way of climbing the stairs – you always step on the last step. So you only need to look at the number of ways of getting to a position from which you can reach the last step i.e. S(n-2)+S(n-1)

## worked it out different

when I first tried this problem I tried seeing how many ways there were to go up with a smaller no. of steps. I finally got the formula: 2 to the power of n. So I did 2 to the power of 10 (no. of steps) and got 1024 (no. of ways to go up 10 steps) . Then I checked the solution and it said there were 89 ways to go up 10 steps! I don't understand what I did wrong!? can somebody please explain??

## response

for 3 steps, the possibilities are 111, 21, and 12. so obviously 2 to the power of n is not a correct formula.

## My answer

My answer is also 89

1111111111

211111111

121111111

112111111

111211111

111121111

111112111

111111211

111111121

111111112

22111111

21211111

21121111

21112111

21111211

21111121

21111112

12211111

12121111

12112111

12111211

12111121

12111112

11221111

11212111

11211211

11211121

11211112

11122111

11121211

11121121

11121112

11112211

11112121

11112112

11111221

11111212

11111122

2221111

2212111

2211211

2211121

2211112

2122111

2121211

2121121

2121112

2112211

2112121

2112112

2111221

2111212

2111122

1222111

1221211

1221121

1221112

1212211

1212121

1212112

1211221

1211212

1211122

1122211

1122121

1122112

1121221

1121212

1121122

1112221

1112212

1112122

1111222

222211

222121

222112

221221

221212

221122

212221

212122

212212

211222

112222

121222

122122

122212

122221

22222

So all of them is 89

## Am I correct tho

My answer is also 89

1111111111

211111111

121111111

112111111

111211111

111121111

111112111

111111211

111111121

111111112

22111111

21211111

21121111

21112111

21111211

21111121

21111112

12211111

12121111

12112111

12111211

12111121

12111112

11221111

11212111

11211211

11211121

11211112

11122111

11121211

11121121

11121112

11112211

11112121

11112112

11111221

11111212

11111122

2221111

2212111

2211211

2211121

2211112

2122111

2121211

2121121

2121112

2112211

2112121

2112112

2111221

2111212

2111122

1222111

1221211

1221121

1221112

1212211

1212121

1212112

1211221

1211212

1211122

1122211

1122121

1122112

1121221

1121212

1121122

1112221

1112212

1112122

1111222

222211

222121

222112

221221

221212

221122

212221

212122

212212

211222

112222

121222

122122

122212

122221

22222

So all of them is 89