Directions: Solve the following problems. All written work must be your own. See the course syllabus for detailed rules.

Let $a_{n}$ be the number of lists of length $n$ with entries in ${0, 1, 2}$ without two consecutive zeros. Note that $a_{0} = 1$ (since the empty list does not have consecutive zeros), $a_{1} = 3$ , and $a_{2} = 8$ (since all $9$ lists of length $2$ are counted except $00$ ).
1. Find a second order homogeneous recurrence relation for $a_{n}$ . In other words, find constants $s$ and $t$ such that $a_{n} = s a_{n - 1} + t a_{n - 2}$ for $n \geq 2$ . Remember to include base cases and argue that your recurrence relation is correct.
2. Use part (a) to explicitly compute $a_{n}$ for $0 \leq n \leq 6$ .
3. Use the characteristic equation method to solve your recurrence in part (a) to find an explicit formula for $a_{n}$ .
Prove that if it is possible to tile an $m \times n$ grid with $4 \times 1$ rectangular tiles, then at least one of the side lengths is divisible by $4$ . (Hint: find a way to color the grid with $4$ colors so that each tile covers one cell of each color.)
For $b \geq 0$ , let $b_{n}$ be the number of ways to tile a $3 \times n$ grid with $1 \times 3$ rectangular tiles. Note that $b_{0} = 1$ , since placing zero tiles counts as a tiling of the $3 \times 0$ grid.
1. Find a recurrence relation for $b_{n}$ . (Your recurrence should include all needed base cases.)
2. Recall that the number of ways $a_{n}$ of tiling a $2 \times n$ grid with dominos is given by the recurrence $a_{0} = a_{1} = 1$ and $a_{n} = a_{n - 1} + a_{n - 2}$ for $n \geq 2$ . How does $b_{n}$ compare with $a_{n}$ , the number of ways to tile a $2 \times n$ grid with dominos? Explain. Can you prove your claim?
[SS 1.3.{8,9}] You work at a car dealership that sells three models: A pickup trick, an SUV, and a compact hybrid. Your job is to park the vehicles in a row. The pickup trucks and the SUVs take up two spaces while the hybrid takes up one space. Let $n$ be a nonnegative integer and let $f (n)$ be the number of ways of arranging vehicles in exactly $n$ spaces, with each space occupied.
1. Find a recurrence relation for $f (n)$ and use it to compute $f (0)$ through $f (10)$ .
2. Find a first-order recurrence relation $g$ that appears to match $f$ (i.e. $g (n)$ should depend only on $g (n - 1)$ ).
3. Prove that $g (n) = f (n)$ by induction.
4. Use the values for $f (0)$ and $f (1)$ to find a candidate formula for $f (n)$ of the form $f (n) = a 2^{n} + b {(- 1)}^{n}$ . Prove that your formula is correct.