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

\showsolutions
%\hidesolutions

\newtheorem{false-theorem}[theorem]{False Theorem}

\begin{document}

\recitation{4}{February 11, 2005}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\insolutions{

%[\stamp]

\section{Strong Induction}

Recall the principle of strong induction:

\textbox{
\textbf{Principle of Strong Induction.}  Let $P(n)$ be a predicate.  If

\begin{itemize}
\item $P(0)$ is true, and
\item for all $n \in \mathbb{N}$, $P(0) \land P(1) \ldots \land
  P(n)$ implies $P(n+1)$,
\end{itemize}
then $P(n)$ is true for all $n \in \mathbb{N}$.
}

As an example, let's derive the fundamental theorem of arithmetic.

\begin{theorem}
  Every positive integer $n \geq 2$ can be written as the product of
  primes.
\end{theorem}

\begin{proof}
  The proof is by strong induction.  Let $P(n)$ be the statement that
  $n$ can be written as the product of primes.

  \noindent \textit{Base case:} $2$ is itself a prime, so $P(2)$ holds.
  
  \noindent \textit{Inductive case:} We show that $P(2) \land P(3)
  \ldots P(n) \implies P(n+1)$ is true.  Assume that $P(2), P(3),
  \dots P(n)$ are true.  Consider $n+1$.  If $n+1$ is a prime number,
  $P(n+1)$ holds.  Otherwise, $n+1$ is a composite number; thus it has
  factors $2 \leq u,v < n+1$ such that $u \cdot v = n+1$.  By the
  inductive hypothesis, $u= \prod_i p_i$ for primes $p_i$ and $v =
  \prod_j p_j$ for primes $p_j$, so therefore, $n+1 = \prod_i p_i
  \cdot \prod p_j$, i.e. $P(n+1)$ is true.  By the principle of strong
  induction, $P(n)$ is true for all $n \geq 2$.
\end{proof}

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

\newpage
}

\section{Problem: Mini-Tetris}

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:

\bigskip
\centerline{\includegraphics[height=0.5in]{rec2-tetrispieces}}
\bigskip

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

\bigskip
\centerline{\includegraphics[height=1.25in]{rec2-2x5wins}}
\bigskip


\noindent \textbf{1.} 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[\vspace{2in}]{
$T_1 = 1$, $T_2 = 3$, and $T_3 = 5$.
}

\noindent \textbf{2.} Express $T_n$ in terms of $T_{n-1}$ and $T_{n-2}$.

\solution[\vspace{3in}]{Every winning configuration on a $2 \times n$
board is of one of the following three types:

\bigskip
\centerline{\includegraphics[height=2in]{rec2-types}}
\bigskip

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

\begin{eqnarray*}
T_n & = & T_{n-1} + 2 T_{n-2}
\end{eqnarray*}
}

\noindent \textbf{3.} Using strong induction, prove that the number 
of winning configurations on a $2 \times n$ Mini-Tetris board ($n \geq
1$) is:

\begin{eqnarray*}
T_n & = & \frac{2^{n+1}+(-1)^n}{3}
\end{eqnarray*}

\solution{The proof is by strong induction on $n$, with the induction
hypothesis $T_n = (2^{n+1}+(-1)^n) / 3$.  The hypothesis is true for
$n = 1$ and $n = 2$, since we determined above that $T_1 = 1 =
(2^{1+1}+(-1)^1)/3$ and $T_2 = 3 = (2^{2+1}+(-1)^2)/3$.

Now suppose $n \geq 2$ and assume that the hypothesis holds for all $k
< n$.  Starting from the equation derived in the preceding problem
part, we have:

\begin{eqnarray*}
T_n     & = &   T_{n-1} + 2 T_{n-2} \\
        & = &   \frac{2^n+(-1)^{n-1}}{3} +
                2 \cdot \frac{2^{n-1}+(-1)^{n-2}}{3} \\
        & = &   \frac{2^n-(-1)^n}{3} +
                \frac{2^n+2(-1)^n}{3} \\
        & = &   \frac{2^{n+1}+(-1)^n}{3}
\end{eqnarray*}

\noindent We use the induction hypothesis twice in the second step,
and then simplify in the third and fourth steps.  This completes the
inductive step.  By strong induction, the hypothesis holds for all $n
\geq 1$.}

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

\newpage

\section{Problem: Breaking a chocolate bar}

We are given a chocolate bar with $m \times n$ squares of
chocolate, and our task is to divide it into $mn$ individual squares.  We
are only allowed to split one piece of chocolate at a time using a
vertical or a horizontal break.

For example, suppose that the chocolate bar is $2 \times 2$.  The
first split makes two pieces, both $2 \times 1$.  Each of these pieces
requires one more split to form single squares.  This gives a total of
three splits.

Use strong induction to conclude the following:
\begin{theorem*}
To divide up a chocolate bar with $m \times n$ squares, we need at
most $m n - 1$ splits.
\end{theorem*}

\solution{This theorem does not immediately lend itself to an
  induction proof, since there are two variables.  In general,
  propositions involving several natural-valued variables can often be
  proved by using a sort of nested induction.  However, in this case,
  we can get by with a single-variable induction and a trick.

Intuitively, to break up a big chocolate bar, we need one split to
make two pieces, and then we can break up the two pieces recursively.
This suggests a proof using strong induction on the {\em size} of the
chocolate bar, where size is measured in chocolate squares.  Now
instead of a problem involving two variables (the two dimensions), we
have a problem in one variable (the size).  With this simplification,
we can prove the theorem using strong induction.

\begin{proof}
The proof is by strong induction on the size of the chocolate bar.  Let
$P(k)$ be the proposition that a chocolate bar of size $k$ requires at
most $k - 1$ splits.  

\emph{Base case, $k=1$}: $P(1)$ is true because there is only a single
square of chocolate, and $1 - 1 = 0$ splits are required.

\emph{Induction step}: We suppose $k \geq 1$ and any chocolate bar of size
$s$, where $1 \leq s \leq k$, requires at most $s-1$ splits.  We must now
show there is a way to split a chocolate bar of size $k+1$ with at most
$k$ splits.

To do this, first break the chocolate bar of size $k+1$ into two smaller
pieces of size $p$ and $q$ where $p + q = k + 1$.  This is certainly
possible because the size of the bar is at least two.  Now the pieces of
sizes $p$ and $q$ are between one and $k$, so by strong induction,
breaking these two pieces into single squares requires only $p - 1$ and $q
- 1$ splits, respectively.  The total number of splits required to break
the bar of size $k+1$ into single squares is therefore at most $1 + (p -
1) + (q - 1) = p + q - 1 = (k + 1) - 1 = k$.

This shows that $P(k)$ implies $P(k+1)$, and the claim is proved by
strong induction.
\end{proof}
}

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

\newpage

\section{Problem: Fibonacci numbers}

The Fibonacci numbers are defined as follows:
\begin{quote}
  $F_1 = 1, F_2 = 1$, and for all $k \geq 3$, $F_k = F_{k-1} + F_{k-2}$.
\end{quote}
The first few terms of the Fibonacci sequence are:
$$1,1,2,3,5,8,13,21,\dots$$
We can't find every single number in the
Fibonacci sequence -- for instance, $4$ is not a number in the
sequence.  But can we express every $n \geq 1$ as the sum of distinct
terms in the Fibonacci sequence?  Indeed, we can!

Use strong induction to prove the following:

\begin{theorem}
  Every $n \geq 1$ can be expressed as the sum of distinct terms in
  the Fibonacci sequence.
\end{theorem}

\solution{
  \begin{proof}
    We proceed by strong induction.  Let $P(n)$ be the statement that
    $n$ can be written as the sum of distinct terms in the Fibonacci
    sequence.

    \noindent \textbf{Base case:} 1 itself is a term in the Fibonacci 
    sequence, so $P(1)$ is true.

    \noindent \textbf{Inductive case:} We want to show that $P(1) 
    \land P(2) \dots P(n) \implies P(n+1)$ is true.  Assume that $P(1), P(2)
    \dots P(n)$ all hold.  Consider $n+1$.  If $n+1$ is a Fibonacci number,
    then we are done.  If not, we have, for some $k \geq 1$, 
    $$F_k < n+1 < F_{k+1}.$$
    This gives us the equation:
    $$n+1 = F_k + (n+1-F_k)$$.  Now $n+1-F_k < n+1$, so by the
    induction hypothesis, $P(n+1 - F_k)$ is true, i.e.
    $$n+1 - F_k = F_{j_1} + F_{j_2} + \ldots.$$
    Furthermore, none of
    the $F_{j_i}$ is $F_k$, since since $n+1 - F_k < F_k$.  Therefore,
    we have that $P(n+1)$ is true, i.e.:
    $$n+1 = F_k + F_{j_1} + F_{j_2} + \dots.$$
    By the principle of strong induction, $P(n)$ is true for all $n$.

  \end{proof}
}

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

\end{document}

