\documentstyle[12pt]{article}
\pagestyle{empty}
\begin{document}
\begin{center}
Math 491, Problem Set \#8: Solutions \\
\end{center}
\medskip
\begin{enumerate}
\item
{\it 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)] {\it Prove that the sequence $a_0,a_1,\dots$
satisfies a linear recurrence relation of order 16 or less.}
For each vertical line through the tiling
that divides one column of height 4 from the next,
there are $2^4=16$ different ways in which
one might see 0 to 4 horizontal dominos
being pierced by the line.
If we give each of these 16 patterns a symbol,
then every domino tiling of a 4-by-$n$ rectangle
is represented by a string of $n+1$ symbols
from an alphabet of size 16,
beginning and ending with the symbol that means
``no horizontal dominos pierced by this line''
(corresponding to the left end and right end of the rectangle);
call this the first symbol.
Conversely, such a codeword corresponds to exactly one tiling
if certain forbidden adjancies do not occur,
and otherwise corresponds to no tilings at all.
Thus the number of (domino-)tilings of the 4-by-$n$ rectangle
is equal to the upper-left entry of the $n$th power
of the 16-by-16 matrix whose $i,j$th entry
tells whether the $i$th symbol can occur
next to the $j$th symbol.
By the Cayley-Hamilton theorem,
the sequence consisting of these entries
must satisfy the 16th-order linear recurrence relation
given by the characteristic polynomial of the matrix.
\item[(b)] {\it Prove that the sequence $a_0,a_1,\dots$
satisfies a linear recurrence relation of order 8 or less.}
To prove this claim,
it's enough to show that half of the 16 symbols
cannot occur in such a codeword
(so that the 16-by-16 matrix can be replaced by an 8-by-8 matrix).
To see this, note that half of the symbols indicate the presence
of an odd number of horizontal dominos
being pierced by a particular vertical line.
That is, if you divide the rectangle in half along the vertical line
and remove the horizontal dominos that the line pierces,
one is left with two sub-regions, each with odd area.
But then these two sub-regions cannot be tiled by dominos
(since a domino has even area).
Hence only 8 of the 16 symbols can occur
in codewords of the form $(1,\dots,1)$,
and the claim is proved.
\item[(c)] {\it Prove that the sequence $a_0,a_1,\dots$
satisfies a linear recurrence relation of order 6 or less.}
Now we show that only 6 of the original 16 symbols
can actually participate in a codeword of the form $(1,\dots,1)$.
Color the constituent squares of the rectangle black and white.
If we have a tiling of the rectangle
and we cut it along a vertical line (discarding the bisected pieces),
the two remaining regions must be tilable by dominos;
so each must contain as many black squares as it contains white squares.
On the other hand, suppose we bisect the rectangle along the same line
and {\it don't\/} discard the bisected pieces;
then (since each column has an even number of squares)
it's clear that each side must contain as many black squares as white.
It follows that, among the bisected dominos,
there must be as many
with a black square on the left and a white square on the right
as there are
with a white square on the left and a black square on the right.
This leaves only six possibilities:
no bisected dominos;
bisected dominos in rows 1 and 2;
bisected dominos in rows 1 and 4;
bisected dominos in rows 3 and 2;
bisected dominos in rows 3 and 4;
and bisected dominos in all four rows.
\item[(d)] {\it Prove that the sequence $a_0,a_1,\dots$
does not satisfy a linear recurrence relation of order 2 or less.}
Suppose there were constants $A,B,C$, not all equal to zero, such that
$A a_n + B a_{n-1} + C a_{n-2} = 0$ for all $n$. Then we must have
$A a_0 + B a_1 + C a_2 = 0$,
$A a_1 + B a_2 + C a_3 = 0$, and
$A a_2 + B a_3 + C a_4 = 0$.
Combining these three scalar equations into a single vector equation,
we get $A (a_0,a_1,a_2) + B (a_1,a_2,a_3) + C (a_2,a_3,a_4) = (0,0,0)$.
This tells us that the three vectors
$(a_0,a_1,a_2)$, $(a_1,a_2,a_3)$, and $(a_2,a_3,a_4)$
must be linearly dependent.
But this would require that the matrix
\[ \begin{array}{ccc}
a_0 & a_1 & a_2 \\
a_1 & a_2 & a_3 \\
a_2 & a_3 & a_2 \end{array} \]
have determinant zero.
We can check that this determinant does not vanish,
since $a_0 = 1$, $a_1 = 1$, $a_2 = 5$, $a_3 = 11$, $a_4 = 36$,
and
\[ \left| \begin{array}{rrr}
1 & 1 & 5 \\
1 & 5 & 11 \\
5 & 11 & 36 \end{array} \right| = 8 \neq 0. \]
Hence such constants $A,B,C$ do not exist,
which proves that the sequence of $a_n$'s
does not satisfy any linear recurrence of degree 2 or less.
\end{itemize}
\end{enumerate}
\end{document}