\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 31, 2025}

%\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 {} [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}

\item 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$).
\begin{enumerate}
	\item Find a second order homogeneous recurrence relation for $a_n$.  In other words, find constants $s$ and $t$ such that $a_n = sa_{n-1} + ta_{n-2}$ for $n\ge 2$.  Remember to include base cases and argue that your recurrence relation is correct.
	\item Use part (a) to explicitly compute $a_n$ for $0\le n \le 6$.  
	\item Use the characteristic equation method to solve your recurrence in part (a) to find an explicit formula for $a_n$.
\end{enumerate}

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

\end{enumerate}
\end{document}
