Due Wed, 10 Apr 2013, at the start of class.
A counter is 2 inches wide and $n$ inches long. You have a pile of 2 inch by 1 inch tiles, and you need to tile the counter. Let $S_n$ be the number of ways to tile a counter $n$ inches long. For example, $S_3=3$, as we see below:
Find a recurrence relation for $S_n$, the number of ways to tile the counter, as well as the appropriate number of starting values so that you could calculate $S_n$ for any $n$. Prove your recurrence relation is correct.