In a resort in Mexico guests may have dinner at three restaurants, the Italian restaurant, the French restaurant or the Brazilian restaurant. Each evening you must eat at one of the restaurants but you may not eat at the French restaurant two nights in a row. Let dn be the number of ways you may eat at the three restaurants over n evenings.

(a) How many eating choices are there for 1, 2 and 3 nights?

(b) Find a recurrence for dn.

(c) Using the recurrence relation, calculate d3, d4 and d5.