5
$\begingroup$

You can climb either $1$ or $2$ stairs at a time, at any given time. How many ways can you get up $11$ stairs?

I've tried using different cases to solve this.

So I did: Case 1: All $1$ steps --> $11 $steps --> number of combinations = $1$

Case 2: $9 $one steps, $1$ two step --> number of combinations = $\binom{n}{2} $??

Case 3: $7$ one steps, $2$ two steps --> number of combinations?

I don't understand how to proceed further. Is there any easier way to do this?

$\endgroup$
6
  • 1
    $\begingroup$ Hint: try the same problem for a shorter staircase ($1$ step, $2$, and so on). You'll see a pattern. $\endgroup$
    – lulu
    Nov 20, 2015 at 14:24
  • 1
    $\begingroup$ You should first define $a_n$ as the number of ways to climb up the steps. Consider the cases when the first step taken is $1$ step and $2$ steps to form a recurrence relation in $a_n$ $\endgroup$
    – Nicholas
    Nov 20, 2015 at 14:25
  • 1
    $\begingroup$ Your case 1 should be ${11+0 \choose 0}$; your case 2 should be ${9+1 \choose 1}$; your case 3 should be ${7+2 \choose 2}$ and so on to ${1+5 \choose 5}$ $\endgroup$
    – Henry
    Nov 20, 2015 at 14:31
  • $\begingroup$ Given a summation with additives $2$ and $1$. How many different ways can you write out the sum, where order matters, such that the sum is $11$? $\endgroup$
    – AlvinL
    Nov 20, 2015 at 14:42
  • 1
    $\begingroup$ This falls under combinatorics and recurrence relations. $\endgroup$
    – Michael Burr
    Nov 20, 2015 at 17:19

6 Answers 6

Reset to default
16
$\begingroup$

Hint: Start at the beginning, not the end.

Step $1$: If there is one step, there is only one way to take the stairs.

Step $2$: If there are two steps, you can either take take $2$ steps or one step twice, leading to two ways to take the stairs.

Step $3$: Consider your first step, if you start with $1$ step, then $2$ steps remain and we know that there are two ways to go up two stairs. On the other hand, if you start with $2$ steps, this leaves one step and we know that there is one way to go up one stair. This gives $1+2=3$ ways to go up three steps.

Step $4$: Consider the first step, if you start with $1$ step, then $3$ steps remain and we know that there are three ways to go up three stairs. On the other hand, if you start with $2$ steps, then there are only two steps left, and we know that there are $2$ ways to go up $2$ steps. This gives $2+3=5$ ways to go up $4$ steps.

Continue in this way. You may recognize the numbers that you get as being in a popular sequence.

$\endgroup$
1
  • 2
    $\begingroup$ Weird, I'd do exactly the same but I'd phrase it very slightly differently so that I was starting at the end. "First consider what happens if you're on step 10. Then consider what happens if you're on step 9. ... Step 0". It's the same dynamic programming solution either way. $\endgroup$
    – Steve Jessop
    Nov 21, 2015 at 0:28
14
$\begingroup$

Here's a way to look at this visually. Draw out the path possibilities:

enter image description here

In this directed graph, you start at step 0 and follow the arrows to step 11. Horizontal arrows represent two steps, and diagonal arrows represent one step. You can see that if a person takes every step, they'll zig zag through the graph. If a person skips as many steps as possible, they'll travel mostly horizontally left-to-right with one diagonal step in there somewhere.

Now let's count the possibilities starting at step 10. There's only one way to go from step 10 to step 11, so let's write 1 next to step 10. There are two ways to go from step 9 to step 11, one of those ways goes through step 10, so let's write 2 next to step 9. From step 8, your options are either to continue to steps 9 or 10. From step 9 you have 2 possibilities to continue to step 11, and from step 10 you have only one. Adding that up means that from step 8 you have 3 possibilities, so let's write 3 next to step 8. Continuing backwards, you can see that at every step, the number of possibilities is the sum of the number of possibilities of the next two immediate steps. Filling this in looks like this:

enter image description here

You can now see that the total number of possibilities is 144.

$\endgroup$
1
  • $\begingroup$ +1 Personally I would do almost the same thing, but starting at the beginning,writing $1$ next to circle 0 since there is only one way to start there, and then go up adding the values from the incoming arrows, so $1$ next to circle 1, $1+1=2$ next to circle 2, $1+2=3$ next to circle 3, $2+3=5$ next to circle 4 and so on until you write $55+89=144$ next to circle 11 $\endgroup$
    – Henry
    Jun 21, 2016 at 16:16
4
$\begingroup$

One can define the $n$-th Fibonacci number (*) as the number of ways you can write $n$ as a sum of $1$'s and $2$'s.

Thus, your answer is the $11$-th Fibonacci number.

(*) Note that there are several definitions of the Fibonacci numbers in common use, so make sure you use the right one, which matches with this definition (note that $F_1 = 1, F_2 = 2$).

$\endgroup$
1
  • 6
    $\begingroup$ You've left out the key step, which is explaining why this definition of the $n$-th Fibonacci number is equivalent to whatever definition you originally learned (probably the inductive one). Without that, you're basically saying that the Fibonacci numbers are the answer because you redefined them to be the answer. $\endgroup$
    – user2357112
    Nov 20, 2015 at 18:31
1
$\begingroup$

In order to follow your original plan:

Case $1$: All $1$-steps, this results in one way to climb the stairs.

Case $2$: $9$ one-steps and $1$ two-step. Since you move $10$ times and one of the moves is a two-step, this gives $\binom{9+1}{1}=\binom{10}{1}$ ways to select the two-step from the $10$ times that you move.

Case $3$: $7$ one-steps and $2$ two-steps. Since you take $9$ moves and two of them are two-steps, you must select which of the steps is a two-step. This gives $\binom{7+2}{2}=\binom{9}{2}$ ways to go up the stairs in this way.

Continue the calculation until you can't add any more two-steps.

$\endgroup$
1
$\begingroup$

The simplest way to solve it Take a look to the picture (link) to see the resolution. This answer is embarrassingly simple (only addition is required, no need to know combinatorics or Fibonaccis).

$\endgroup$
0
$\begingroup$

The most we can step two at a time is five times. We have a sequence: $$2,2,2,2,2,1$$ How many different ways can it be ordered? Keep in mind, the pattern of the sequence has to change with each substitution.

Then we can step two stairs four times: $$2,2,2,2,1,1,1$$

.. and so on until you step two times only once and the rest are single steps. Count the number of possibilities for each scenario and add them together and add one to the result. Why?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .