Staircase recursion problem using recurrence relations. 
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?
 A: 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?
