\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}
\usepackage{graphicx}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}

\begin{document}
\headers{Math378}{Homework 2}{Due Fri. Jan 30, 2026}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\makeatletter
\def\@oddfoot{}
\makeatother

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

\begin{enumerate}

\item {} 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.)

\item {} [SS 1.3.1] Let $a_0 = 0$ and $a_n = 3a_{n-1} + 2$ for $n\ge 1$.
\begin{enumerate}
	\item Find the first few values of the sequence $a_n$ and use this to guess a general formula.
	\item Use induction to prove that your general formula from part (a) is correct.
\end{enumerate}


\end{enumerate}
\end{document}
