1. (16 points total - 2 points each) In each situation, write a recurrence relation, including base case(s), that describes the recursive structure of the problem. Briefly explain how you obtain your recurrence. You do not need to solve for the closed-form formula. Note: For parts (g) and (h) of this problem, to "tile a rectangle" is to cover it with tiles so that no tiles overlap, no tiles are hanging off the edge of the rectangle, and every space on the rectangle is covered by some tile (a.) Let C(n) be the number of 1 x 1 cells in an n x n grid. Write a recurrence for C(n) (b.) A bunch of motorcycles and cars want to parallel park on a street. The street can fit n motorcycles, but cars take up three motorcycle spaces. Let A(n) be the number of arrangements of cars and motorcycles on a street that fits n motorcycles. For example, A(5)4 because there are four ways to park vehicles on a street with five motorcycle spaces. If M stands for motorcycle, and C stands for car, then the four arrangements are: MMC, MCM, CMM, and MMMMM. Write a recurrence for A(n) (c.) Let B(n) be the number of length n binary strings that have no three consecutive 0s Write a recurrence for B(n)