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

%\hidesolutions
\showsolutions

\begin{document}

\recitation{12}{March 18, 2005}

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

\insolutions{
\section{Solving linear recurrences}

\paragraph{Guessing a \emph{particular solution}.}
Recall that a general linear recurrence has the form:
%
\[
f(n) = a_1 f(n - 1) + a_2 f(n - 2) + \cdots + a_d f(n - d) + g(n)
\]
%
As explained in lecture, one step in solving this recurrence is
finding a \textit{particular solution}; i.e., a function $f(n)$ that
satisfies the recurrence, 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 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}
In practice, your first or second guess will almost always work.


\paragraph{Dealing with \emph{repeated roots}.}
In lecture we saw that the solutions to a linear recurrence are
determined by the roots of the characteristic equation: For each
root~$r$ of the equation,
\begin{center}
the function $r^n$ is a solution to the recurrence.
\end{center}
Taking a linear combination of these solutions, we can 
move on to find the coefficients. 

\noindent
The situation is a little more complicated when $r$ is a
\emph{repeated root} of the characteristic equation: if its
multiplicity is $k$, then (not only $r^n$, but)
\begin{center}
each of the functions 
$
\;\; r^n,
\;\; n r^n,
\;\; n^2 r^n,
\;\; \ldots,
\;\; n^{k-1} r^n
\;\;
$
is a solution to the recurrence,
\end{center}
so that our linear combination must use all of them.


\newpage
}

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

\section{Mini-Tetris (again)}

Remember Mini-Tetris from Recitation~4? Here is an overview: A {\em
winning configuration} in the game 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, the several possible winning configurations on a $2\times
5$ board include:
\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}
In that past recitation, we had defined $T_n$ to be the number of
different winning configurations on a $2 \times n$ board. Then we
had to inductively prove $T_n$ equals some particular closed form
expression. Remember that expression? Probably not. But no damage,
now you can find it on your own.
\begin{itemize}

\item[(a)] 
Determine the values of $T_1$, $T_2$, and $T_3$.

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

\item[(b)] 
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}
\]
}

\item[(c)]
Find a closed-form expression for $T_n$.

\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, the
closed form expression for $T_n$ is 
\[
T_n = \frac23 2^n + \frac13 (-1)^n = \frac{2^{n+1} + (-1)^n}{3}.
\]
Remember it now? 
}

\end{itemize}



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

\instatements{\newpage}

\section{Inhomogeneous linear recurrences}
Find a closed-form solution to the following linear recurrence.
\begin{align}
T_0 & = 0 \notag\\
T_1 & = 1 \notag\\
T_{n} & = T_{n-1} + T_{n-2} + 1\tag{*}
\end{align}

\begin{itemize}

\item[(a)]
First find the general solution to the corresponding homogenous recurrence.

\solution[\vspace{2.5in}]{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.
\]
}

\item[(b)]
Now find a particular solution to the inhomogenous recurrence.

\solution[\vspace{1in}]{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~(*). 
}

\item[(c)]
The complete solution to the recurrence is the homogenous solution
plus the particular solution. Use the initial conditions to find the
coefficients. 

\solution[\vspace{2in}]{
\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*}
}


\item[(d)]
Therefore, the complete solution to the recurrence is:

\solution[\vspace{4em}]{
\[
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
        \left( \frac{1 - \sqrt{5}}{2} \right)^n - 1.
\]
}

\end{itemize}

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

\instatements{\newpage}

\section{Back to homogeneous ones}

Let's get back to homogeneous linear recurrences. Find a closed-form
solution to this one. 
\begin{align*}
S_0 & = 0 \\
S_1 & = 1 \\
S_n & = 6 S_{n-1} - 9 S_{n-2}
\end{align*}
Anything strange?

\solution{
The characteristic polynomial is $r^2-6r+9 = (r-3)^2$, so we have a
\emph{repeated root}: $r=3$, with multiplicity $2$. 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}.
\]
}


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

\input{short_guide}

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

\end{document}
