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