This problem was asked in a job interview for a software engineering position at Google.

There is a staircase with 100 steps. How many ways can you walk from the bottom to the top of the staircase if you are only allowed to take one step and two steps at a time?

### Like this:

Like Loading...

*Related*

## 6 comments

Comments feed for this article

November 10, 2010 at 2:55 pm

WadeWarning, math ahead!

This problem can be solved by summing over all possible ways to walk the steps with 50-100 steps (it will take 50 steps if you take 2 steps always, 100 if you take 1 step always). There is only one way to get to the top using 50 steps: take 2 steps always. To take 51 steps, you must take 2 steps 49 times and 1 step twice. There are ways to do this (just choose when you will take each 1 step). Keep going in this fashion. For 52 steps you remove a 2 step and replace it with two 1 steps. When you take 60 steps, the only way to do this is to take 2 steps 40 times, and 1 step 20 times. The number of ways to do this is . Thus, the solution to this problem is , since each time you add another step, you are adding two more 1 steps, and we need to choose where all the 1 steps go. Using this method one could easily generalize the problem to climbing a staircase size n in a given number of 1 or 2 steps. Richard, notice that this is the 101st Fibonacci number! Come up with a combinatorial proof that the number of ways to climb a staircase of n using steps size 1 or 2 is given by the n+1st Fibonacci number. Mathematical induction will surely help.

November 10, 2010 at 7:03 pm

RichardI have two comments.

First, to come up with a generalized formula for counting the number of ways to climb a staircase of size taking only one or two steps, we can simply mimic your argument replacing with Doing so yields the formula

Showing that this is the Fibonacci number is a little trickier and leads to my second comment.

For notation, we denote by the Fibonacci number. Suppose you are confronted with a staircase of size Then there is only one way to climb it, which is equal to . Suppose you are confronted with a staircase of size Then there are two ways to climb it. Namely,

1. two one steps or

2. one two step,

which is equal to Suppose you are confronted with a staircase of size Then there are three ways to climb it. Namely,

1. three one steps,

2. one two step and one one step, or

3. one one step and one two step,

which is equal to Continuing in this manner we can proceed by induction on In doing so we see that for a staircase of size there are many ways to climb the staircase taking only one or two steps.

To see a full analysis of this problem, click here. You’ll find a very beautiful result using generating functions ; )

November 11, 2010 at 12:59 am

WadeYou just said you can prove it by using induction but never did so 😛

November 10, 2010 at 3:06 pm

WadeBy the way, once you’ve found a combinatorial proof for the Fibonacci numbers we’ve come up with a summation to find the nth Fibonacci number where n is even (I’m sure you tweak it a little bit to work for odds too, but here you go): 2Nth Fibonacci number is given by .

November 19, 2010 at 2:52 pm

RRi’ve been told that in these types of interview questions, they aren’t looking for the answer as much as they are looking for your approach to the problem.

November 19, 2010 at 4:14 pm

RichardAgreed. Being a math student though, I thought it would be fun to actually solve the problem 🙂