Exercise 6

While walking up stairs you notice that you have a habit of using 3 ways of taking one step and 4 ways of taking two steps at a time. Find a recurrence relation for the number of ways to go up $n$ steps. Solve the recurrence relation given the initial conditions of $a_0 = 1$ and $a_1 = 3$ using the characteristic root method.