Climbing 100 Steps

Date: 05/01/2003 at 12:02:08
From: Matt
Subject: Combinatorics

Find the number of ways in which you can climb 100 steps if you can 
go up 1 or 2 steps at a time.

I was thinking that n = 100 steps and there are two choices for each 
step you land on, but I wasn't sure how to break it down using 1 step 
and 2 steps at a time. I figured that there must be an even number of 
1-steps and of course an even number of 2-steps to make 100, but I 
lost it there.

Date: 05/01/2003 at 14:34:24
From: Doctor Robert
Subject: Re: Combinatorics

Start with an easier problem. Let's just have 10 steps. Then a table 
will show the number of 1-step and 2-step jumps needed.

                  1-step      2-step

                    10           0
                     8           1
                     6           2
                     4           3
                     2           4
                     0           5

Now the question is, "For each of these possibilities, how many ways 
can the different steps be arranged?" There's only one way to do the 
steps one at a time. There are nine ways to do eight one-step and one 
2-step jumps. These numbers turn out to be C(10,0), C(9,1), 
respectively. For the next, the possibilities number C(8,2) or 28.  
C(7,3)= 35  C(6,4) = 15  C(5,0) = 1. The total number of ways is 
therefore 1+9+28+35+15+1 = 89 ways for TEN steps.  

Good luck on the ONE HUNDRED steps.  There might be a clever way to 
find the sum without doing all the grunt work.

- Doctor Robert, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 05/01/2003 at 17:43:11
From: Doctor Douglas
Subject: Re: Combinatorics

Hi Matt,

Thanks for writing to the Math Forum.

I'd like to supplement Dr. Robert's answer. There is another way to 
approach this problem, which is to try to enumerate the number of ways 
to reach a given step.  

  step    ways to get there
  ----    -----------------
   1            1            (has to be a 1-step)
   2            2            (either a 2-step, or two 1-steps)
   3            3            (either 1+1+1, 1+2, or 2+1)
   4            5            (1+1+1+1, 1+2+1, 2+1+1, 1+1+2, 2+2)
   5            8                Why?

The reason is that in order to get to step 5, we must either get to 
step 3 (and take a 2-step), or get to step 4 (and take a 1-step).  
Thus the number of ways to get to step 5 is the number of ways to get 
to step 3 plus the number of ways to get to step 4:

  N(5) = N(4) + N(3)

The case of getting to step 3 and then taking a 1-step and then
another 1-step is counted in the number of ways to get to step 4.

Let's continue the table:

   6           13
   7           21
   8           34
   9           55
  10           89          (so Dr. Robert's method is verified)
  11          144
  
Do these numbers look familiar? If they do, they should - it is a
Fibonacci sequence, and the answer to your question is the hundredth
(or perhaps the 101st, depending on how you index things) Fibonacci
number.

I'm sure you'll agree that this method is somewhat less work
computationally than going through the entire combinatorial list.

- Doctor Douglas, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 05/01/2003 at 19:31:22
From: Matt
Subject: Combinatorics

Thanks for the prompt replies; you guys are awesome. After seeing the 
numbers that were sent from that method, I figured I could use 
recurrence equations and get an answer a lot quicker for the 100 
steps. It came out to be a messy answer but I'm almost 100% sure 
it's correct. I'm a mathematics major and your help will help me get 
a better grade on my final tomorrow no doubt. Thanks again.