
\section{Strong induction}

\subsection{The Method}

Now we define an apparently-more-powerful variant on the ordinary
induction principle\.  Recall ordinary induction:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 0 [P(n)]$ \\
1. (Base) $P(0)$ \\
2. (Inductive step) $\forall n \geq 0 [P(n) \Rightarrow P(n+1)]$ \\
3. QED                        
\> \> \> \> \> Induction 
\end{tabbing}
Strong induction gives an alternative way to prove the same kind of
statement:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 0 [P(n)]$ \\
1. (Base) $P(0)$ \\
2. (Inductive step) 
$\forall n \geq 0 [(\forall i, 0 \leq i \leq n (P(i))) \Rightarrow P(n+1)]$ \\
3. QED                        
\> \> \> \> \> Strong induction 
\end{tabbing}
The implication within the inductive step is easier to show than it is
for ordinary induction, because now in order to prove $P(n+1)$, we get to
assume all of the hypotheses $P(0),P(1),P(2),\ldots,P(n)$, not just
$P(n)$\.  This is written like a new deduction rule\.  We can also
write it as an axiom:
\[
[P(0) \wedge 
 \forall n \geq 0 [(\forall i, 0\leq i \leq n (P(i))) \Rightarrow P(n+1)]] 
\Rightarrow \forall n [P(n)]. 
\]

The concept of strong induction should be distinguished from the
previously discussed concept of strengthening the hypothesis\.  Strong
induction is a specific inference rule.  Strengthening the hypothesis
is a general paradigm for tackling induction problems.  

Why does this method work\?  Well, we want to prove for $0, 1, 2,
\ldots$\.  We get $P(0)$ for free\.  Then we know $P(0) \Rightarrow
P(1)$, which tells us $P(1)$ (modus ponens)\.  Then we know $P(0)
\wedge P(1) \Rightarrow P(2)$, which, since we know $P(0) \wedge
P(1)$, tells us $P(2)$\.  Etc\.

Of course, we can do the same thing starting from any $k$, not just
$0$: 
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq k [P(n)]$ \\
1. (Base) $P(k)$ \\
2. (Inductive step) 
$\forall n \geq k [(\forall i, k \leq i \leq n (P(i))) \Rightarrow P(n+1)]$ \\
3. QED                        
\> \> \> \> \> Strong induction 
\end{tabbing}

\subsection{Nim}

The game of Nim is defined as follows: Some positive number of sticks
are placed on the ground.  Two players take turns removing one, two,
or three sticks.  The player to remove the last stick loses.

\begin{theorem}
The first player loses if the number of sticks, $n$, is $4k+1$ for some $k$,
and wins (if he plays optimally) otherwise.
\end{theorem}

We can formalize this by defining a strategy as a rule for how many
sticks to remove when there are $n$ left\.  We then show that if $n=4k+1$, 
then player 2 has a strategy that will force a win for him, otherwise, 
player 1 has a strategy that will force a win for him.

\begin{proof}
We show that if $n=4k+1$ the first player loses, 
and if $n = 4k$, $4k + 2$, or $4k + 3$, the first player wins\. 
This exhausts all possible cases for $n$.

Proceed by strong induction, starting from $1$. \\
Base case: $n = 1$. 
The first player has no choice but to remove $1$ stick and lose, which
is what the theorem says for this case. \\
\\
Strong inductive step: \\
Suppose the theorem is true for numbers $1$ through $n$ and show that it
is true for $n+1$\. 
For the inductive step, there are four cases: 
\begin{itemize}
\item $n+1=4k+1$: show that the first player loses.  
We've already handled the base case ($1$) so we can assume $n+1 \geq 5$\.  
Consider what the first player might do to win: he can choose
to remove 1, 2 or 3 sticks\.  
If he removes one stick, the remaining number of sticks is $n = 4k$\. 
By strong induction, the player who plays at this point should win (if
he uses his best strategy)\.  
So the player who played first will lose\.

Similarly, if the first player removes two sticks, the remaining
number is $4(k-1)+3$.  Again, he loses, by the same reasoning.  \\ 
Similarly, by removing $3$ sticks, he loses.  \\ 
So, however the first player moves, he loses.

\item $n+1 = 4k$: show that the first player can win.

Have the first player remove 3 sticks: the second player then sees
$4(k-1)+1$ sticks, and loses, by the strong inductive hypothesis.

\item $n+1 = 4k+2$: show that the first player can win.

Have the first player remove 1 stick: the second player then sees
$4k + 1$ sticks, and loses as in the previous case. 

\item $n+1 = 4k+3$: show that the first player can win.

Have the first player remove 2 sticks: again, the second player sees
$4k + 1$ sticks and loses.
\end{itemize}
\end{proof}


\subsection{Prime Factorization}

Recall that a prime is a number not evenly divisible by any number but
itself and one\.  $2, 3, 5, 7, 11, \ldots$ are primes\.  $4, 6, 8, 9,
10, 12, \ldots$ are not\.  They are composites. \\
Notice, however, that each composite can be broken down (factored)
into primes\.  E.g., $12 = 2 \times 2 \times 3$\.    This is not a
coincidence.

\begin{theorem}
Every natural number $\geq 2$ can be written as the product of one or
more primes.
\end{theorem}

\begin{proof}
We use strong induction, starting from $2$, where $P(n)$ is the
  predicate
``$n$ can be written as the product of one or more primes''.
\begin{tabbing}\\
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove:  $\forall n \geq 2 [P(n)]$ \\
1. $P(2)$
\> \> \> \> \> Use $2$ itself \\
2. $\forall n \geq 2 [(\forall i, 2 \leq i \leq n) (P(i)) \Rightarrow P(n+1)]$ \\
\> 1. Fix $n \geq 2$ \\
\> 2. Assume $\forall i, 2 \leq i \leq n [P(i)]$, that is, all numbers up to \\
\> \> and including $n$ can be factored into primes \\
\> 3. $P(n+1)$, that is, $n+1$ can be factored into primes. \\
\>  \> \> \> \> ??? \\
\> 4. QED
     \> \> \> \> Implication, UG \\
3. QED
    \> \> \> \> Strong induction 
\end{tabbing}
The argument about factoring $n+1$ breaks down into cases, depending on
whether or not $n+1$ itself is prime:
\begin{tabbing}\\
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> 3. $P(n+1)$, that is, $n+1$ can be factored into primes. \\
\> \> 1. If $n + 1$ is prime, then $n+1$ can be factored into primes. \\

\> \> \> \> \> Use $n+1$ itself \\
\> \> 2. If $n+1$ is not prime, then $n+1$ can be factored into primes.
\\
\> \> \> 1. Assume $n+1$ is not prime. \\
\> \> \> 2. $n+1$ can be written as $a \times b$, where $1 < a, b < n+1$
\\
\> \> \> \> \> Definition of ``prime'' \\
\> \> \> 3. $a$ can be factored into primes. 
      \> \> Strong inductive hypothesis (2.2) \\
\> \> \> 4. $b$ can be factored into primes. 
         \> \> Strong inductive hypothesis (2.2) \\
\> \> \> 5. $n+1$ can be factored into primes. 
         \> \> Use all the factors from $a$ and $b$.  \\
\> \> \> 6. QED
            \> \> Implication \\
\> \> 3. QED
        \> \> \> Cases
\end{tabbing}

We can do step 5 a little more carefully\.  If $a$ is written as a
product $2^{a_2} 3^{a_3} 5^{a_5} \cdots$ and $b$ is written as a
product $2^{b_2} 3^{b_3} 5^{b_5} \cdots$ then $n+1 = ab$ is written as
$2^{a_2+b_2} 3^{a_3+b_3} 5^{a_5+b_5} \cdots$\.  We just add the number
of occurrences of each separate prime factor.
\end{proof}

\begin{example}
A factorization of $144$ can be obtained by noticing that $144 = 8
\times 18$ (among other possibilities)\.
$8$ can be written as $2^3$, and $18$ as $2 \times 3^2$\.
So, write $144$ as $2^{3+1} 3^2$, or $2^4 3^2$.
\end{example}

\subsection{Block towers}

Given an unlimited number of blocks of heights $3$ and $7$, what
height towers can be built?\\
\\
Try some possible heights: \\
1: no \\
2: no \\
3: yes, 3 \\
4: no \\
5: no \\
6: 3+3 \\
7: 7 \\
8: no \\
9: 3+3+3 \\
10: 3 + 7 \\
11: no \\
12: 3+3+3+3 \\
13: 7+3+3\\
14: 7+7\\
15: 3+3+3+3+3 \\
16: 7+3+3+3 \\
\\
From this point on, can we make all larger height towers? \\
Define $P(n)$ to be ``we can build a tower of height $n$''\.
We prove this by strong induction:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 12 (P(n))$ \\
1. (Base) $P(12)$ 
\> \> \> \> \> Use 3+3+3+3 \\
2. (Inductive step) 
$\forall n \geq 12 
   [(\forall i, 12 \leq i \leq n (P(i))) \Rightarrow P(n+1)]$ \\
3. QED                        
\> \> \> \> \> Strong induction 
\end{tabbing}
Here's the idea for the inductive step\.  We can build a tower of
height $n-2$, by strong inductive hypothesis, then add one $3$-block\.  That
is, use $P(n-2)$ to show $P(n+1)$\.  But there's a catch: this works
only if $n-2 \geq 12$, i.e., $n \geq 14$\.  (We can only assume $P$
for arguments $\geq 12$.)

For $n = 12, 13$, need to make special arguments.

So, we really have an argument by cases, within the inductive step:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
2. (Inductive step) 
$\forall n \geq 12 
   [(\forall i, 12 \leq i \leq n (P(i))) \Rightarrow P(n+1)]$ \\
\> 1. Fix $n \geq 12$. \\
\> 2. $(\forall i, 12 \leq i \leq n (P(i))) \Rightarrow P(n+1)$ \\
\> \> 1. Assume $\forall i, 12 \leq i \leq n (P(i)$ \\
\> \> 2. $P(n+1))$ \\ 
\> \> \> 1. $n = 12 \Rightarrow P(n+1)$ 
         \> \> Use 7+3+3 \\
\> \> \> 2. $n = 13 \Rightarrow P(n+1)$ 
         \> \> Use 7+7 \\
\> \> \> 3. $n \geq 14 \Rightarrow P(n+1)$ 
         \> \> ??? \\
\> \> \> 4. QED
         \> \> Cases \\
\> \> 3. QED 
      \> \> \> Implication \\
\> 3. QED
   \> \> \> \> UG
\end{tabbing}
The first two special cases are easy---we've already done them\.
The last case is the one covered by the idea sketched earlier.
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> \> 3. $n \geq 14 \Rightarrow P(n+1)$ \\
\> \> \> \> 1. Assume $n \geq 14$. \\
\> \> \> \> 2. $P(n-2)$
            \> By inductive hypothesis 2.2.1 and the fact \\
\> \> \> \> \> that $n-2 \geq 12$ \\
\> \> \> \> 3. $P(n+1)$
            \> Add one block to the tower from the \\
\> \> \> \> \> previous step. \\
\> \> \> \> 4. QED
            \> Implication
\end{tabbing}

\noindent Look at the logical structure\.  I wrote this as a single
base case (for 12) and inductive step, where the inductive step breaks
down into two special cases (for 13 and 14) plus the rest\.
I could also formulate a variant on the proof rule: 
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 12 (P(n))$ \\
1. (Base) $P(12)$ \\
2. (Base) $P(13)$ \\
3. (Base) $P(14)$ \\
4. (Inductive step) $\forall n \geq 14
   [(\forall i, 12 \leq i \leq n (P(i))) \Rightarrow P(n+1)]$ \\
3. QED                        
\> \> \> \> \> Very specialized strong induction
\end{tabbing}
