\documentclass[12pt]{article}
\usepackage{light}

\hidesolutions
%\showsolutions

\begin{document}

\recitation{12}{October 22, 2004}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\insolutions{
\section*{Guessing a Particular Solution}

A general linear recurrence has the form:
%
\[
f(n) = b_1 f(n - 1) + b_2 f(n - 2) + \ldots + b_d f(n - d) + g(n)
\]
%
One step in solving this recurrence is finding a \textit{particular
solution}.  This is a function $f(n)$ that satisfies the recurrence
equation, but may not be consistent with the boundary conditions.
Here's a recipe to help you guess a particular solution:

\begin{itemize}

\item If $g(n)$ is a constant, guess that $f(n)$ is some constant $c$.
Plug this into the recurrence equation and see if any constant
actually works.  If not, try $f(n) = b n + c$, then $f(n) = a n^2 + b
n + c$, etc.

\item More generally, if $g(n)$ is a polynomial, try a polynomial of
the same degree.  If that fails, try a polynomial of degree one
higher, then two higher, etc.  For example, if $g(n) = n$, then try
$f(n) = b n + c$ and then $f(n) = a n^2 + b n + c$.

\item If $g(n)$ is an exponential, such as $3^n$, then first guess
that $f(n) = c3^n$.  Failing that, try $f(n) = b n 3^n + c 3^n$ and
then $a n^2 3^n + b n 3^n + c 3^n$, etc.

\end{itemize}

\noindent In practice, your first or second guess will almost always
work.

\newpage
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Mini-Tetris}

\begin{problem}
A {\em winning configuration} in the game of Mini-Tetris is a complete
tiling of a $2 \times n$ board using only the three shapes shown
below:

\begin{center}
\unitlength=0.25in
\begin{picture}(11,2)
\thicklines
\put(0,0){\framebox(2,2){}}
\put(5,0){\framebox(1,2){}}
\put(9,0){\framebox(2,1){}}
\thinlines
\put(1,0){\line(0,1){2}}
\put(0,1){\line(1,0){2}}
\put(5,1){\line(1,0){1}}
\put(10,0){\line(0,1){1}}
\end{picture}
\end{center}

For example, here are several possible winning configurations on a $2
\times 5$ board:

\begin{center}
\unitlength=0.25in
\begin{picture}(12,5)
\thicklines
\put(0,0){\framebox(2,1){}}
\put(0,1){\framebox(2,1){}}
\put(0,2){\framebox(2,1){}}
\put(0,3){\framebox(2,1){}}
\put(0,4){\framebox(2,1){}}
\put(5,0){\framebox(1,2){}}
\put(6,0){\framebox(1,2){}}
\put(5,2){\framebox(2,1){}}
\put(5,3){\framebox(1,2){}}
\put(6,3){\framebox(1,2){}}
\put(10,0){\framebox(2,1){}}
\put(10,1){\framebox(2,2){}}
\put(10,3){\framebox(1,2){}}
\put(11,3){\framebox(1,2){}}
\end{picture}
\end{center}

\bparts

\ppart Let $T_n$ denote the number of different winning configurations
on a $2 \times n$ board.  Determine the values of $T_1$, $T_2$, and
$T_3$.

\solution[\newpage]{
$T_1 = 1$, $T_2 = 3$, and $T_3 = 5$.
}

\ppart Find a recurrence equation that expresses $T_n$ in terms of
$T_{n-1}$ and $T_{n-2}$.

\solution[\vspace{2.5in}]{Every winning configuration on a $2 \times
n$ board is of one three types, distinguished by the arrangment of
pieces at the top of the board.

\begin{center}
\begin{picture}(200,100)
\thicklines
\put(0,0){\framebox(40,100){}}
\put(80,0){\framebox(40,100){}}
\put(160,0){\framebox(40,100){}}
\put(0,80){\framebox(40,20){}}
\put(80,60){\framebox(20,40){}}
\put(100,60){\framebox(20,40){}}
\put(160,60){\framebox(40,40){}}
\put(20,40){\makebox(0,0){$n-1$}}
\put(100,30){\makebox(0,0){$n-2$}}
\put(180,30){\makebox(0,0){$n-2$}}
\end{picture}
\end{center}

There are $T_{n-1}$ winning configurations of the first type, and there
are $T_{n-2}$ winning configurations of each of the second and third
types.  Overall, the number of winning configurations on a $2 \times n$
board is:
\[
T_n = T_{n-1} + 2 T_{n-2}
\]
}

\ppart Find a closed-form expression for the number of winning
configurations on a $2 \times n$ Mini-Tetris board.

\solution[\vspace{4in}]{
The characteristic polynomial is $r^2-r-2 = (r-2)(r+1)$, so the solution
is of the form $A2^n + B(-1)^n$.  Setting $n=1$, we have $1 = T_1 = 2A -
B$.  Setting $n=2$, we have $3 = T_2 = A2^2+B(-1)^2 = 4A+B$.  Solving
these two equations, we conclude $A=2/3$ and $B=1/3$.  That is,
\[
T_n = \frac23 2^n + \frac13 (-1)^n = \frac{2^{n+1} + (-1)^n}{3}.
\]
}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\instatements{\newpage}

\begin{problem} Find closed-form solutions to the following linear
recurrences.

\bparts

\ppart
\begin{align}
T_0 & = 0 \notag\\
T_1 & = 1 \notag\\
T_{n} & = T_{n-1} + T_{n-2} + 1\tag{*}
\end{align}

\solution[\newpage]{First, we find the general solution to the homogenous
recurrence.  The characteristic equation is $r^2 - r - 1 = 0$.  The
roots of this equation are:
\begin{eqnarray*}
r_1	& = &	\frac{1 + \sqrt{5}}{2} \\
r_2	& = &	\frac{1 - \sqrt{5}}{2}
\end{eqnarray*}

Therefore, the solution to the homogenous recurrence is of the form
\[
T_n = A \left( \frac{1 + \sqrt{5}}{2} \right)^n +
		B \left( \frac{1 - \sqrt{5}}{2} \right)^n.
\]

Next, we need a particular solution to the inhomogenous recurrence.
Since the inhomogenous term is constant, we guess a constant solution, $c$.
So replacing the $T$ terms in~(*) by $c$, we require
\[
c = c + c + 1,
\]
namely, $c=-1$.  That is, $T_n \equiv -1$ is a particular solution to~(*).
The complete solution to the recurrence is the homogenous solution
plus the particular solution:

\begin{eqnarray*}
T_n	& = &	A \left( \frac{1 + \sqrt{5}}{2} \right)^n +
		B \left( \frac{1 - \sqrt{5}}{2} \right)^n - 1
\end{eqnarray*}

All that remains is to find the constants $A$ and $B$.  Substituting
the initial conditions gives a system of linear equations.

\begin{eqnarray*}
0	& = &	A + B - 1 \\
1	& = &	A \left( \frac{1 + \sqrt{5}}{2} \right) +
		B \left( \frac{1 - \sqrt{5}}{2} \right) - 1
\end{eqnarray*}

The solution to this linear system is:

\begin{eqnarray*}
A	& = &	\frac{5 + 3 \sqrt{5}}{10} \\
B	& = &	\frac{5 - 3 \sqrt{5}}{10}
\end{eqnarray*}

Therefore, the complete solution to the recurrence is
\[
T_n  = 	\left( \frac{5 + 3 \sqrt{5}}{10} \right) \cdot
        \left( \frac{1 + \sqrt{5}}{2} \right)^n +
        \left( \frac{5 - 3 \sqrt{5}}{10} \right) \cdot
        B \left( \frac{1 - \sqrt{5}}{2} \right)^n - 1.
\]
}

\ppart
\begin{align*}
S_0 & = 0 \\
S_1 & = 1 \\
S_n & = 6 S_{n-1} - 9 S_{n-2}
\end{align*}

\solution{
The characteristic polynomial is $r^2-6r+9 = (r-3)^2$, so the solution is
of the form $A3^n + Bn3^n$ for some constants $A$ and $B$.  Setting
$n=0$, we have $0 = S_0 = A3^0 +B\cdot 0\cdot 3^0=A$.  Setting $n=1$, we have
$1 = S_1 = A3^1+B\cdot 1\cdot 3^1 = 3B$, so $B=1/3$.  That is,
\[
S_n = 0\cdot 3^n + \frac13 \cdot n3^n= n3^{n-1}.
\]
}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\input{short_guide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
