Results 1 to 2 of 2

Math Help - Stairs problem (recurrence)

  1. #1
    Junior Member
    Joined
    Aug 2009
    Posts
    28

    Stairs problem (recurrence)

    Consider a staircase with n stairs which one can clim by 2 stairs or by 3 stairs at each step. e.g. a staircase with n=9 stairs can be climbed in exactly 5 ways.
    Write a recurrence relation for the number of ways to ascend this staircase.
    I worked out the values for [Consider a staircase with n stairs which one can clim by 2 stairs or by 3 stairs at each step. e.g. a staircase with n=9 stairs can be climbed in exactly 5 ways.
    Write a recurrence relation for the number of ways to ascend this staircase.

    I worked out the values for Q_{n} up to 9:
    Q_{0}= 0
    Q_{1}= 0
    Q_{2}= 1
    Q_{3}= 1
    Q_{4}= 1
    Q_{5}= 2
    Q_{6}= 2
    Q_{7}= 3
    Q_{8}= 4
    Q_{9}= 5

    which gave me Q(n) = Q(n-2) + Q(n-3) but I think this is wrong.

    Please double-check my values for Q_{n}/help me solve this!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by DaRush19 View Post
    Consider a staircase with n stairs which one can clim by 2 stairs or by 3 stairs at each step. e.g. a staircase with n=9 stairs can be climbed in exactly 5 ways.
    Write a recurrence relation for the number of ways to ascend this staircase.
    I worked out the values for [Consider a staircase with n stairs which one can clim by 2 stairs or by 3 stairs at each step. e.g. a staircase with n=9 stairs can be climbed in exactly 5 ways.
    Write a recurrence relation for the number of ways to ascend this staircase.

    I worked out the values for Q_{n} up to 9:
    Q_{0}= 0
    Q_{1}= 0
    Q_{2}= 1
    Q_{3}= 1
    Q_{4}= 1
    Q_{5}= 2
    Q_{6}= 2
    Q_{7}= 3
    Q_{8}= 4
    Q_{9}= 5

    which gave me Q(n) = Q(n-2) + Q(n-3) but I think this is wrong.

    Please double-check my values for Q_{n}/help me solve this!
    Your recurrence relation is correct!

    Think about the last step, that takes one to the top of the staircase. It covers either the top two stairs or the top three stairs. So to climb a flight of n stairs, you either climb the first n2 stairs, followed by a 2-stair step; or you climb the first n3 stairs, followed by a 3-stair step. Think about the number of ways of doing that, and you'll see where the recurrence relation came from.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence problem
    Posted in the Calculators Forum
    Replies: 2
    Last Post: November 24th 2009, 02:53 AM
  2. grid of stairs
    Posted in the Algebra Forum
    Replies: 11
    Last Post: August 13th 2009, 06:55 AM
  3. Please Help! Recurrence Problem!
    Posted in the Algebra Forum
    Replies: 1
    Last Post: February 25th 2009, 02:44 PM
  4. Recurrence Problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 15th 2006, 06:10 AM
  5. Stairs puzzle
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: March 30th 2005, 03:25 PM

Search Tags


/mathhelpforum @mathhelpforum