Find a recurrence for the number of ways to arrange cars in a row with $n$ parking spaces

Question

Find a recurrence for the number of ways to arrange cars in a row with $n$ parking spaces if we can use Cadillacs or Hummers or Fords. A Hummer requires two spaces, while a Cadillac or Ford requires just one space.

I know I need to use a recurrence relation model such as $$a_n=a_{n-1}-a_{n-2}$$ but I don't know how to apply the concept to to this question fully. I have done a little bit of preliminary work but I do not know if it is necessarily correct:

We can assume that$$a_1 = 2$$Since given 1 space we can put either a Cadillac or a Ford. And we can also assume that$$a_2 = 5$$Since given 2 spaces, we can put CC, CF, FC, FF, or H. But where do I go from here?

Answer 1

To fill a parking lot with $n$ spaces, you can either:

1. Fill the first $n-1$ spaces and then put a Cadillac or a Ford at the end; there are $2 \cdot a_{n-1}$ ways to do this ($a_{n–1}$ ways to fill the first $n-1$ spaces, and $2$ ways to fill the last space)
2. Fill the first $n-2$ spaces and then put a Hummer at the end; there are $a_{n-2}$ ways to do this

Adding the two, we get $$a_n = 2a_{n-1} + a_{n-2}$$