You have a supply of 1" x 1" tiles in two different colors and of 1" x 2" tiles in three different colors; this is five different colors altogether. Suppose you put enough tiles together in a straight line so that the result is 1" x n". How many different patterns could you make? (Don't worry about putting two 1x1 tiles of the same color next to each other and having that be indistinguishable from a 1x2 tile of the same color)

a) Write a recurrence for the number of patterns.

b) Solve it using the technique of the characteristic equation.

Draw some patterns on paper to see "what is going on". That is, start with n = 1, then n = 2, then n = 3 and so forth. What are the initial conditions?