Staircase recursion problem using recurrence relations.

Question

How many ways can we climb a staircase with 8 steps if we can take either 1 or 2 steps at a time? Hint: Count the different ways according to the number of steps you take take when you start your climb.

I believe the answer is

$$n = a_0 (n-1)+a_1(n-2)$$ for the general equation, now do i solve this using standard method of solving recurrence relations, by solving for $a_0$ and $a_1$ and the $r$ values after using the characteristic equation? Please help me understand this problem?

Answer 1

Formulating the Recurrence

Let $a_n$ denote the number of ways to climb $n$ stairs. Since we can take one or two steps at a time, let's look at what happens on the first turn.

• If we take 1 step, we are left with $(n-1)$ stairs to climb, which can be done in $a_{n-1}$ ways.
• If we take 2 stepa, we are left with $(n-2)$ stairs to climb, which can be done in $a_{n-2}$ ways.

Since these cases are non-overlapping and cover the entire possible set of outcomes we must have $$ a_n = a_{n-1} + a_{n-2} $$ and it is trivial to check there is one way to climb one stair, so $a_1=1$, and two ways to climb two stairs (either take a 2-step or two 1-steps), so $a_2 = 2$.

This is the famous Fibonacci sequence.

---

Solving the Recurrence

If you assume $a_n = r^n$ and substitute into the recurrence equation, you get $$ r^n = r^{n-1} + r^{n-2} \iff r^2 = r+1, $$ and so now you can find $r$ using the quadratic formula. Let's say you get two possible answers, $m$ and $M$.

Therefore, $a_n = Am^n + BM^n$ (where $M,n$ are known to you already, $n$ is a variable and $A,B$ are some constants). To find the value of the constants $A,B$, plug in $$ \begin{split} 1 &= a_1 = Am + BM\\ 2 &= a_2 = Am^2 + BM^2 \end{split} $$ so you have 2 equations for 2 unknowns.

Can you finish now?