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

1. Two players play a game on a row of $n$ cells, alternating turns. In each turn, a player marks one unmarked cell that is not next to marked cell. A player with no legal moves available loses. Prove that if $n$ is odd, then the first player has a winning strategy. (Hint: give an explicit, non-inductive winning strategy for the first player when $n$ is odd. The general game is tricky to analyze.)

2. [SS 1.3.1] Let $a_0=0$ and $a_n=3a_{n-1}+2$ for $n\ge 1$.

   1. Find the first few values of the sequence $a_n$ and use this to guess a general formula.
   2. Use induction to prove that your general formula from part (a) is correct.