# Homework Help: How many ways can I go up some steps?

1. Oct 30, 2009

### Paulo Serrano

1. The problem statement, all variables and given/known data
A person can go up one step at a time, skip a step at a time, or skip two steps at a time, with the exception of the final step, which obviously you can only go one step up.

a) Calculate the different ways someone can up up a staircase with 7 steps.
b) Calculate the number of steps in the staircase if the total number of ways I can go up it is N=987

2. Relevant equations

none

3. The attempt at a solution

2. Oct 30, 2009

### flatmaster

With only 7 steps, I think a case-wise solution may be quicker.

3. Oct 31, 2009

### Paulo Serrano

This was from the test to major in physics/engineering from Rio De Janeiro Federal University last year. The answer sheet says you have to use Fibonacci numbers. I have no idea what those are or how they work, so I'm going to read about them on wikipedia.

if someone can give me a summary of how it works, though, I'd appreciate it.

4. Nov 1, 2009

### willem2

Fibonacci numbers are numbers form a sequence of numbers, the first 2 are
f(0) = 0 and f(1) = 1 and the rest is computed by f(n) = f(n-1) + f(n-2).
This is called a recurrence relation
The numbers you'll get are related with a similar relation.

If you want to go up a staircase of n steps with n at least 3, the first step could move up 1, 2 or 3 steps. The number of ways is the sum of the number of ways to climb the smaller steps that are left.

Unfortunately, question b makes me think that the author of this problem DOES think that the numbers are from the fibonacci sequence, wich is wrong. It would be right if you could move only 1 or 2 steps up at a time.