Results 1 to 2 of 2

Math Help - Recursion

  1. #1
    Newbie Chief65's Avatar
    Joined
    Sep 2008
    From
    Denver
    Posts
    18

    Recursion

    We just finished induction and are now starting on Recursive functions. The assigned problem is: How many ways is it possible to climb a staircase if n steps if one is allowed to take either one or two steps at a time?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by Chief65 View Post
    We just finished induction and are now starting on Recursive functions. The assigned problem is: How many ways is it possible to climb a staircase if n steps if one is allowed to take either one or two steps at a time?
    Call a_n the ways of getting to the nth step.

    Suppose we want to climb to the nth step, and n\geq{2}.

    There are 2 possible ways of getting there:


    1. We are at the n-1 step, and we jump to the next. a_{n-1} ways of doing this, since we have to get to the n-1 step
    2. We are at the n-2 step, and we jump directly to n. a_{n-2} ways of doing this

    So we have a_{n}=a_{n-1}+a_{n-2}

    Now a_0=1 (there's one way of doing nothing) and a_1=1 and our sequence is determined
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recursion help.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 28th 2010, 02:23 PM
  2. recursion
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 13th 2009, 07:00 AM
  3. Recursion Depth
    Posted in the Algebra Forum
    Replies: 0
    Last Post: October 27th 2009, 11:01 AM
  4. transfinite recursion
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 25th 2009, 07:57 PM
  5. Recursion
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 30th 2008, 09:40 PM

Search Tags


/mathhelpforum @mathhelpforum