Climbing a n-stair staircase, taking 2 or 3 stairs each step...


Yeah, your recurrence relation looks correct. If I'm standing on stair $n$, how did I get here? I either came from stair $n-2$ or stair $n-3$, so the number of possible ways to get to stair $n$ is equal to the number of ways to get to stair $n-2$ plus the number of ways to get to stair $n-3$.

You are missing are the first couple of inputs. Think of the first couple of stairs. If I'm standing at stair 0, how many ways are there to get to stair 1? How about stair 2? How about stair 3?

If $a_n$ denotes the number of ways to get to stair $n$, your recurrence relation is as follows:

$a_1 = 0$
$a_2 = 1$
$a_3 = 1$
and the general case,
$a_n = a_{n-2} + a_{n-3}$ for all $n \geq 4$.


Related videos on Youtube

Author by


just looking for some help in my upper division courses.

Updated on August 01, 2022


  • D.Peterson
    D.Peterson over 1 year

    Suppose a person has a n-stair staircase to climb, and they can go up exactly 2 or 3 stairs each time they take a step. Generate some initial data. Find and explain the recurrence relation to describe how many different ways there are to traverse the n-stair staircase. What is the auxiliary equation for this recurrence relation? What is the closed form solution?

    I have this question on my test review packet and I am a bit lost on how to do it. Any advice or hints would be appreciated. Thanks in advance!

    My first thoughts were something along the lines of: a sub n = a sub n - 2 + a sub n - 3 as the recurrence relation since you can only step 2 or 3 stairs at a time I was also wondering if there as a condition of n >= 2 since any staircase with less than 2 steps is not traversable.

  • D.Peterson
    D.Peterson about 8 years
    So I understand that what you have shown is the recurrence relation along with the initial conditions. I was unable to complete the auxiliary equation method though. I seemed to get stuck while plugging in the initial conditions while trying to reach the final auxiliary equation.
  • PT272
    PT272 over 7 years
    From mathematica you could solve this recurrence equation to get an explicit formula using a command with something like this: RSolve[{a[n] == a[n - 2] + a[n - 3], a[1]=0, a[2] == a[3] == 1}, a[n], n] Does anybody have mathematica here, or you need to go through the work of setting up the generating functions and polynomials.