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

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

\begin{document}
\headers{Math378}{Homework 3}{Due Fri. Feb 6, 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 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.)

\item For $b\ge 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.  
\begin{enumerate}
	\item Find a recurrence relation for $b_n$.  (Your recurrence should include all needed base cases.)
	\item 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\ge 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?
\end{enumerate}

\item {} [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. 
\begin{enumerate}
	\item Find a recurrence relation for $f(n)$ and use it to compute $f(0)$ through $f(10)$.
	\item Find a first-order recurrence relation $g$ that appears to match $f$ (i.e. $g(n)$ should depend only on $g(n-1)$).
	\item Prove that $g(n)=f(n)$ by induction.
	\item Use the values for $f(0)$ and $f(1)$ to find a candidate formula for $f(n)$ of the form $f(n) = a2^n + b(-1)^n$.  Prove that your formula is correct.
\end{enumerate}

\end{enumerate}
\end{document}
