\hyperdef{strong}{induction}{\section{Strong Induction}}

%\subsection*{The Strong Induction Principle}

A useful variant of induction is called {\em strong induction}.  Strong
Induction and Ordinary Induction are used for exactly the same thing:
proving that a predicate $P(n)$ is true for all $n \in \naturals$.

\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 \naturals$, $P(0)$, $P(1)$, \dots, $P(n)$
\emph{together} imply $P(n+1)$,
\end{itemize}

then $P(n)$ is true for all $n \in \naturals$.
}

The only change from the ordinary induction principle is that strong
induction allows you to assume more stuff in the inductive step of your
proof!  In an ordinary induction argument, you assume that $P(n)$ is true
and try to prove that $P(n+1)$ is also true.  In a strong induction
argument, you may assume that $P(0)$, $P(1)$, \dots, and $P(n)$ are
\textit{all} true when you go to prove $P(n+1)$.  These extra assumptions
can only make your job easier.

\subsection{Products of Primes}

As a first example, we'll use strong induction to prove one of those
familiar facts that is almost, but maybe not entirely, obvious:
\begin{lemma}\label{prim}
Every integer greater than 1 is a product of primes.
\end{lemma}
Note that, by convention, any number is considered to be a product
consisting of one term, namely itself.  In particular, every prime is
considered to be a product whose terms are all primes.

\begin{proof}

We will prove Lemma~\ref{prim} by strong induction, letting the induction
hypothesis, $P(n)$, be
\[
n+2 \text{ is a product of primes}.
\]
So Lemma~\ref{prim} will follow if we prove that $P(n)$ holds for all $n
\geq 0$.

\textbf{Base Case:} $P(0)$ is true because $0+2$ is prime, and so is a
product of primes by convention.

\textbf{Inductive step:} Suppose that $n \geq 0$ and that $i+2$ is a
product of primes for every nonnegative integer $i < n+1$.  We must show that
$P(n+1)$ holds, namely, that $n+3$ is also a product of primes.  We argue
by cases:

If $n+3$ is itself prime, then it is a product of primes by convention, so
$P(n+1)$ holds in this case.

Otherwise, $n + 3$ is not prime, which by definition means $n+3 = km$ for
some integers $k,m$ such that $2 \leq k,m < n+3$.  Now $0 \leq k-2 < n+1$,
so by strong induction hypothesis, we know that $(k-2)+2=k$ is a product of
primes.  Likewise, $m$ is a product of primes.  it follows immediately that
$km = n+3$ is also a product of primes.  Therefore, $P(n+1)$ holds in this
case as well.

So $P(n+1)$ holds in any case, which completes the proof by strong
induction that $P(n)$ holds for all nonnegative integers, $n$.

\end{proof}

Despite the name, strong induction is technically no more powerful than
ordinary induction, though it makes some proofs easier to follow.  But any
theorem that can be proved with strong induction could also be proved with
ordinary induction (using a slightly more complicated induction
hypothesis).  On the other hand, announcing that a proof uses ordinary
rather than strong induction highlights the fact that $P(n+1)$ follows
directly from $P(n)$, which is generally good to know.

\subsection{Making Change}

The country Inductia, whose unit of currency is the Strong, has coins
worth 3\sg\ (3 Strongs) and 5\sg.  Although the Inductians have some
trouble making small change like 4\sg\ or 7\sg, it turns out that they can
collect coins to make change for any number at least 8 Strongs.

Strong induction makes this easy to prove for $n+1 \ge 11$, because then
$(n+1)-3 \ge 8$, so by strong induction the Inductians can make change for
exactly $(n+1)-3$ Strongs, and then they can add a 3\sg\ coin to get
$(n+1)\sg)$.  So the only thing to do is check that they can make change
for all the amounts from 8 to 10\sg, which is not too hard to do.

Here's a detailed writeup using the official format:

\begin{proof}

  We prove by strong induction that the Inductians can make change for any
  amount of at least 8\sg.  The induction hypothesis, $P(n)$ will be:
\begin{quote}
If $n \geq 8$, then there is a collection of coins whose value is $n$
Strongs.
\end{quote}

Notice that $P(n)$ is an implication.  When the hypothesis of an
implication is false, we know the whole implication is true.  In this
situation, the implication is said to be \emph{vacuously} true.  So $P(n)$
will be vacuously true whenever $n < 8$.\footnote{Another approach that
avoids these vacuous cases is to define
\[
P'(n) \eqdef \text{there is a collection of coins whose value is $n+8$
Strongs}
\]
and prove that $P'(n)$ holds for all $n \geq 0$.
\iffalse
The solution to
\href{http://courses.csail.mit.edu/6.042/spring06/solutions/cp3fsol.pdf}
{Class Problem 1 from Spring '06, Friday, Feb. 24} uses this approach.\fi
}

We now proceed with the induction proof:

\textbf{Base case:} $P(0)$ is vacuously true.

\textbf{Inductive step:}  We assume $P(i)$ holds for all $i \leq n$, and
prove that $P(n+1)$ holds.  We argue by cases:

\textbf{Case} ($n+1 < 8$): $P(n+1)$ is vacuously true in this case.

\textbf{Case} ($n+1$ = 8): $P(8)$ holds because the Inductians can use one
3\sg\ coin and one five\sg\ coins.

\textbf{Case} ($n+1$ = 9): Use a three 3\sg\ coins.

\textbf{Case} ($n+1$ = 10): Use two 5\sg\ coins.

\textbf{Case} ($n+1 \geq 11$): Then $n \geq (n+1) -3 \geq 8$, so by the
strong induction hypothesis, the Inductians can make change for $(n+1)-3$
Strong.  Now by adding a 3\sg\ coin, they can make change for $(n+1)\sg$.

So in any case, $P(n+1)$ is true, and we conclude by strong induction that
for all $n \geq 8$, the Inductians can make change for $n$ Strong.

\end{proof}


\subsection{Unstacking}

Here is another exciting 6.042 game that's surely about to sweep the
nation!

\hyperdef{stack}{game}{You} begin with a stack of $n$ boxes.  Then you
make a sequence of moves.  In each move, you divide one stack of boxes
into two nonempty stacks.  The game ends when you have $n$ stacks, each
containing a single box.  You earn points for each move; in particular, if
you divide one stack of height $a + b$ into two stacks with heights $a$
and $b$, then you score $ab$ points for that move.  Your overall score is
the sum of the points that you earn for each move.  What strategy should
you use to maximize your total score?

As an example, suppose that we begin with a stack of $n = 10$ boxes.
Then the game might proceed as follows:
%
\[
\begin{array}{cccccccccccl}
\multicolumn{10}{c}{\textbf{Stack Heights}} & \quad & \textbf{Score} \\
\underline{10}&&&&&&&&& && \\
5&\underline{5}&&&&&&&& && 25 \text{ points} \\
\underline{5}&3&2&&&&&&& && 6 \\
\underline{4}&3&2&1&&&&&& && 4 \\
2&\underline{3}&2&1&2&&&&& && 4 \\
\underline{2}&2&2&1&2&1&&&& && 2 \\
1&\underline{2}&2&1&2&1&1&&& && 1 \\
1&1&\underline{2}&1&2&1&1&1&& && 1 \\
1&1&1&1&\underline{2}&1&1&1&1& && 1 \\
1&1&1&1&1&1&1&1&1&1 && 1 \\ \hline
\multicolumn{10}{r}{\textbf{Total Score}} & = & 45 \text{ points}
\end{array}
\]
%
On each line, the underlined stack is divided in the next step.  Can
you find a better strategy?

\subsubsection{Analyzing the Game}

%Hide in full version
%You will see in class how to use strong induction to analyze this game of
%blocks.
%end Hide

%\iffalse  %unHide after Friday lecture:

Let's use strong induction to analyze the unstacking game.  We'll prove
that your score is determined entirely by the number of boxes ---your
strategy is irrelevant!

\begin{theorem}\label{stacking}
Every way of unstacking $n$ blocks gives a score of $n(n-1)/2$ points.
\end{theorem}

There are a couple technical points to notice in the proof:

\begin{itemize}

\item The template for a strong induction proof is exactly the same as
for ordinary induction.

\item As with ordinary induction, we have some freedom to adjust indices.
In this case, we prove $P(1)$ in the base case and prove that $P(1),
\dots, P(n)$ imply $P(n+1)$ for all $n \geq 1$ in the inductive step.

\end{itemize}

\begin{proof}
The proof is by strong induction.  Let $P(n)$ be the proposition that
every way of unstacking $n$ blocks gives a score of $n(n-1)/2$.

\textbf{Base case:} If $n = 1$, then there is only one
block.  No moves are possible, and so the total score for the game is
$1(1 - 1)/2 = 0$.  Therefore, $P(1)$ is true.

\textbf{Inductive step:} Now we must show that $P(1)$, \dots, $P(n)$ imply
$P(n+1)$ for all $n \geq 1$.  So assume that $P(1)$, \dots, $P(n)$ are all
true and that we have a stack of $n+1$ blocks.  The first move must split
this stack into substacks with positive sizes $a$ and $b$ where $a+b =
n+1$ and $0<a,b\leq n$.  Now the total score for the game is the sum of
points for this first move plus points obtained by unstacking the two
resulting substacks:
%
\begin{align*}
\text{total score}
    & = \text{(score for 1st move)} \\
    & \quad + \text{(score for unstacking $a$ blocks)} \\
    & \quad + \text{(score for unstacking $b$ blocks)} \\
    & = ab + \frac{a(a-1)}{2} + \frac{b(b-1)}{2} & \text{by $P(a)$ and $P(b)$}\\
    & = \frac{(a+b)^2-(a+b)}{2} = \frac{(a+b)((a+b)-1)}{2}\\
    & = \frac{(n+1)n}{2}
\end{align*}
%
This shows that $P(1)$, $P(2)$, \dots, $P(n)$ imply $P(n+1)$.

Therefore, the claim is true by strong induction.
\end{proof}
%\fi  %end unHide

\begin{notesproblem}
%TBA   %Hide after Friday lecture

%\iffalse %unhide after Friday lecture:
Define the \term{potential}, $p(S)$, of a stack, $S$, of blocks to be
$k(k+1)/2$ where $k$ is the number of blocks in $S$.  Define the
potential, $p(A)$, of a set, $A$, of stacks to be the sum of the
potentials of the stacks in $A$.

Generalize Theorem~\ref{stacking} to show that for any set, $A$, of
stacks, if a sequence of moves starting with $A$ leads to another set,
$B$, of stacks, then the score for this sequence of moves is $p(A)-p(B)$.
%\fi  %end friday unHide
\end{notesproblem}

\endinput
