Exercise 10

Let $a_n$ be the number of $1 \times n$ tile designs you can make using $1 \times 1$ squares available in 4 colors and $1 \times 2$ dominoes available in 5 colors.

1. First, find a recurrence relation to describe the problem. Explain why the recurrence relation is correct (in the context of the problem).

2. Write out the first 6 terms of the sequence $a_1, a_2, \ldots$.

3. Solve the recurrence relation. That is, find a closed formula for $a_n$.