How many ways can I go up some steps?

[Paulo Serrano]

Homework Statement

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

Homework Equations

none

The Attempt at a Solution

 

[flatmaster]

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

 

[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.

 

[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, which is wrong. It would be right if you could move only 1 or 2 steps up at a time.