Associated Topics || Dr. Math Home || Search Dr. Math

### 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.
```
Associated Topics:
College Discrete Math

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search