\documentstyle[12pt]{article}
\pagestyle{empty}
\begin{document}
\begin{center}
Math 491, Problem Set \#5 \\
(due 9/25/03)
\end{center}
\medskip
Let $a_n$ be the number of domino tilings of a 3-by-$2n$ rectangle,
and let $b_n$ be the number of domino tilings of
a 3-by-$(2n+1)$ rectangle from which a corner square has been removed.
We showed in class that
$a_n=a_{n-1}+2b_{n-1}$
and
$b_n=a_{n-1}+3b_{n-1}$
for all $n \geq 1$.
\begin{enumerate}
\item
Introduce $$A(x) = a_0 + a_1 x + a_2 x^2 + \dots$$
and $$B(x) = b_0 + b_1 x + b_x x^2 + \dots.$$
Write down two algebraic relations between $A(x)$ and $B(x)$
that represent the two recurrence relations
(taking care to incorporate the boundary conditions correctly),
and solve for $A(x)$ and $B(x)$.
\item
We also saw in class that
$$
\left( \begin{array}{c} a_n \\ b_n \end{array} \right)
= \left( \begin{array}{cc} 1 & 2 \\ 1 & 3 \end{array} \right)^n
\left( \begin{array}{c} 1 \\ 1 \end{array} \right) .
$$
Use linear algebra to derive
a formula for $a_n$.
\end{enumerate}
\medskip
\noindent
Please be sure to write down how many hours you spent working on the assignment,
and whom you worked with.
\end{document}