\documentstyle[12pt]{article}
\begin{document}
\begin{center}
Math 491, Problem Set \#5: Solutions
\end{center}
\medskip
{\it 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
{\it 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)$.}
The coefficient of $x^n$ in
$A(x)-xA(x)-2xB(x)$ is $a_n-a_{n-1}-2b_{n-1}=0$ when $n \geq 1$
and is $a_0 = 1$ when $n=0$;
the coefficient of $x^n$ in
$B(x)-xA(x)-3xB(x)$ is $b_n-a_{n-1}-3b_{n-1}=0$ when $n \geq 1$
and is $b_0 = 1$ when $n=0$.
So we have $(1-x)A(x)-2xB(x)=1$
and $xA(x)+(3x-1)B(x)=-1$.
Solving, we get
$$A(x) = \frac{1-x}{1-4x+x^2}$$
and
$$B(x) = \frac{1}{1-4x+x^2}.$$
The roots of the denominator of $A(x)$ are
$2 \pm \sqrt{3}$,
whose reciprocals are one another;
so the coefficients of $A(x)$ can be expressed in the form
$a_n = C \alpha^n + D \beta^n$
where $\alpha = 2 + \sqrt{3}$
and $\beta = 2 - \sqrt{3}$
and where $C,D$ are some undetermined constants
(calculated in problem 2).
\item
{\it 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$.}
The eigenvalues of the matrix are the roots of
$(\lambda-1)(\lambda-3)-(-2)(-1)=0$,
or $\lambda^2 - 4 \lambda + 1$.
Hence for any row vector $v$ and column vector $w$
(both of length 2),
the scalar $v\ M^n\ w$ must be of the form
$C \alpha^n + D \beta^n$,
where $\alpha,\beta$ are the roots of $\lambda^2-4\lambda+1=0$
(say $\alpha = 2+\sqrt{3}$ and $\beta = 2-\sqrt{3}$)
and the coefficients $C,D$ are determined by the choice of $v$ and $w$.
Setting $v = [1,0]$ and $w = [1,1]^T$,
we see that $a_n$ must be given by such a formula.
To solve for $C$ and $D$, set $n=0$ and $n=1$
to get $C=\frac12+\frac{\sqrt{3}}{6}$
and $D=\frac12-\frac{\sqrt{3}}{6}$.
Hence
$$a_n =
\left(\frac12+\frac{\sqrt{3}}{6}\right)(2+\sqrt{3})^n
+\left(\frac12-\frac{\sqrt{3}}{6}\right)(2-\sqrt{3})^n.$$
\end{enumerate}
\medskip
\noindent
\end{document}