1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How many ways can I go up some steps?

  1. Oct 30, 2009 #1
    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. jcsd
  3. Oct 30, 2009 #2
    With only 7 steps, I think a case-wise solution may be quicker.
     
  4. Oct 31, 2009 #3
    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.
     
  5. Nov 1, 2009 #4
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook