\documentstyle[12pt]{article}
\pagestyle{empty}
\begin{document}
\begin{center}
Math 192r, Problem Set \#6 \\
(due 10/9/01)
\end{center}
\medskip
\begin{enumerate}
\item
For each even integer $n \geq 2$,
we can represent each domino tiling of a 3-by-$n$ rectangle
by a code $(a_1,a_2,\dots,a_n)$,
where $a_k$ is the number of vertical dominos
in the $k$th column (always either 0 or 1).
Note that two different tilings can have the same code;
e.g., for $n=2$
there are three tilings but only two codes
(namely $(0,0)$ and $(1,1)$).
Formulate a conjecture for the number of codes
that occur for general $n$.

\item
Let $a_n$ be the number of domino tilings
of a 4-by-$n$ rectangle, with $n \geq 0$
(we put $a_0 = 1$ by convention).
\begin{itemize}
\item[(a)] Prove that the sequence $a_0,a_1,\dots$
satisfies a linear recurrence relation of order 16 or less.
\item[(b)] Prove that the sequence $a_0,a_1,\dots$
satisfies a linear recurrence relation of order 8 or less.
\item[(c)] Prove that the sequence $a_0,a_1,\dots$
satisfies a linear recurrence relation of order 6 or less.
\end{itemize}

\end{enumerate}

\end{document}

