## Climbing Up Some Stairs

Have you ever been up a really long set of stairs? Usually when walking on these stairs, we tend to go up either 1 or 2 steps at a time, and especially when on such a long set of stairs, will inevitably use a mixture of both. Here’s a great problem which I read recently, and thought had some cool ideas behind it. How many possible ways are there to get up 100 steps if you go up in increments of 1 or 2? A computer scientist would probably think in terms of recursion, and a mathematician would think of permutations and combinations. How would you start to think about this? Don’t scroll below the picture if you don’t want to see the solution, and I highly suggest trying it out yourself.

Let’s start with the most obvious route: all 1’s. This gives one possibility, and then of we add a 2 into the mix we get 99 more possibilities (there are now 99 step increments, and we have to choose one for the two to be placed). Upon adding another step of 2, there are 98 from which we have to choose two to be the 2’s, so we have 98 choose 2 possibilities (this is simply 98!/(2!*96!), which we know by the binomial theorem or combinatorics: try figuring out a formula for combinations yourself if you haven’t come across this, and you’ll get the same). Keep going the same way until you have 50 steps of 2, and add up all the possibilities. This is one way to do it, and quite easily gives you the answer. But there’s another cooler way to do it.

Let’s think about how to get to each individual step. How many ways are there to get to the first step? Well, 1. What about the second step? You can go from the first step, or go directly there, so 2 ways. Now the third step: You can get to the third step either from the first step or from the second, so you simply add up the number of ways to get to the first and second, which is three. Well for the fourth one, you can get there from either the second or third, so that’s 2+3=5. The sixth goes the same way, and is 3+5=8. Notice anything? This is just the Fibonacci series. So the number of ways to get to the 100th step is just the 101th number (the first number of this sequence is the second of the Fibonacci series) of the Fibonacci series. Damn…