\documentclass[11pt,twoside]{article}
\usepackage{/a/class/6.042/fall00/newlectures/macros-course-lectures}

\renewcommand{\thepage}{\arabic{page}}

%\makeslides

\begin{document}

\onlystudents

\lecture{notes3}{Proof by Induction, continued}{September 14, 2000}

\noindent
Topics for today:
\begin{itemize}
\item
More (regular) inductive proofs
\item
Strong induction
\item
Strong induction proof examples
\end{itemize}

\reading{Velleman 6.3, 6.4; Rosen 3.2}

Last time we introduced the basic structure of a proof by induction,
and did some basic examples\.  
Today we'll continue with more basic examples of inductive proofs\.  
Then we'll go on to two fancier forms of induction,
called strong induction and structural induction\.

Last time, I forgot to mention a feature of the tiling example:
It not only showed the existence of a tiling---it actually gave a
recipe for {\em producing\/} one. \\
Example:  To tile a $2^3 \times 2^3$ square leaving the upper right
corner empty, divide it into 4, put one tile in the center, and
recursively tile the 4 pieces, each with one square missing.
[[[Diagram]]]

%[[[Anyone want to draw a helpful diagram?]]]

Inductive proof here yields a recursive tiling algorithm.

\section{More Regular Inductive Proofs}

The examples in this section involve functions that are defined recursively.

\subsection{Fibonacci numbers}

The Fibonacci number are interesting numbers that arise, e.g., in
biology, where they model some types of growth processes (plants,
cells, rabbit populations,...)\.  The Fibonacci numbers are written as
$F_i$, $i = 0, 1, 2, \ldots$\.  They are defined recursively by: \\ 
\begin{align*}
F_0 &= 0\\ 
F_1 &= 1\\ 
F_i &= F_{i-1} + F_{i-2} \mbox{ for $i \geq 2$.} 
\end{align*}
So the sequence starts out $0, 1, 1, 2, 3, 5, 8, 13, 21,\ldots$. \\

The Fibonacci numbers satisfy many cute identities, so they provide
lots of fun for mathematicians\.  For example:
\begin{theorem}
$\forall n \geq 0 (\Sigma_{i=0}^n F_i^2 = F_n F_{n+1})$
\end{theorem}

Example: $n = 4$: \\
$0^2 + 1^2 + 1^2 + 2^2 + 3^2 = 15 = 3 \cdot 5$\.
\\
Let's try a proof by induction\.  The theorem statement suggests
trying it with $P(n)$ defined as: 
\[\sum_{i=0}^n F_i^2 = F_n F_{n+1}
\]

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 0 (\Sigma_{i=0}^n F_i^2 = F_n F_{n+1})$ \\
1. (Base) $\Sigma_{i=0}^0 F_i^2 = F_0 F_1$ \\
2. (Inductive step) $\forall n \geq 0
   (\Sigma_{i=0}^n F_i^2 = F_n F_{n+1} \Rightarrow
    \Sigma_{i=0}^{n+1} F_i^2 = F_{n+1} F_{n+2})$ \\
\> \> \> \> \> ??? \\
3. QED               
\> \> \> \> \> Induction
\end{tabbing}

\noindent Now we stare at the gap between $P(n)$ and $P(n+1)$\.
$P(n+1)$ is given by a summation that's obtained from that for $P(n)$
by adding one term; this suggests that, once again, we subtract.  The
difference is just the term $F_{n+1}^2$\.  Now, we are assuming that
the original $P(n)$ summation totals $F_n F_{n+1}$ and want to show
that the new $P(n+1)$ summation totals $F_{n+1} F_{n+2}$\.  So we
would {\em like\/} the difference to be
\[
F_{n+1} F_{n+2} - F_n F_{n+1}
\]

So, the actual difference is $F_{n+1}^2$ and the difference we want is
$F_{n+1} F_{n+2} - F_n F_{n+1}$\.  Are these the same\?  We want to
check that:
\[
F_{n+1}^2 = F_{n+1} F_{n+2} - F_n F_{n+1}
\]
But this is true, because it is really the Fibonacci definition in
disguise: to see this, divide by $F_{n+1}$\.  Here's the complete
proof:

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 0 (\Sigma_{i=0}^n F_i^2 = F_n F_{n+1})$ \\
1. (Base) $\Sigma_{i=0}^0 F_i^2 = F_0 F_1$ 
\> \> \> \> \> Both sides are $0$. \\
2. (Inductive step) $\forall n \geq 0 
   (\Sigma_{i=0}^n F_i^2 = F_n F_{n+1} \Rightarrow
    \Sigma_{i=0}^{n+1} F_i^2 = F_{n+1} F_{n+2})$ \\
\> 1. Fix $n \geq 0$. \\
\> 2. Assume $\Sigma_{i=0}^n F_i^2 = F_n F_{n+1}$ \\
\> 3. $\Sigma_{i=0}^{n+1} F_i^2 = F_{n+1} F_{n+2}$ \\
\> \> 1. $\Sigma_{i=0}^{n+1} F_i^2 = \Sigma_{i=0}^n F_i^2 + F_{n+1}^2$
      \> \> \> Summation has one extra term \\
\> \> 2. $\Sigma_{i=0}^n F_i^2 + F_{n+1}^2 = F_n F_{n+1} + F_{n+1}^2$
      \> \> \> Inductive hypothesis (2.2) \\
\> \> 3. $F_n F_{n+1} + F_{n+1}^2 = F_{n+1}(F_n + F_{n+1})$
      \> \> \> Algebra \\
\> \> 4. $F_{n+1}(F_n + F_{n+1}) = F_{n+1} F_{n+2}$ 
      \> \> \> Fibonacci definition \\
\> \> 5. QED                         
      \> \> \> Combining the equations \\
\> 4. QED 
   \> \> \> \> Implication, UG \\
3. QED                           
\> \> \> \> \> Induction
\end{tabbing}

\subsection{Double Induction}

Here's a trickier use of induction, used twice, in a nested way, in
the same proof\.
Define a function of two natural number variables recursively as follows: \\
$f(0,k) = 1$ for all $k \geq 0$. \\
$f(n,0) = 1$ for all $n \geq 0$.\\
For $n, k \geq 0,$  $f(n+1,k+1) = f(n,k+1) + f(n+1,k)$. \\
\\
Why does this define a function\?  We can see by looking at a table\.
The first two rules fill in the first row and column, respectively\.
For each other entry, you obtain the value by adding bottom and left
neighbors\.  It is left to the reader to see that this defines a
unique function, that is, fills in all the spaces, in exactly one
way.
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXX\=   \kill
4  |\> 1   \> 5  \> 15  \> 35  \> 70 \\
3  |\> 1   \> 4  \> 10  \> 20  \> 35 \\
2  |\> 1   \> 3  \>  6  \> 10  \> 15 \\
1  |\> 1   \> 2  \>  3  \>  4  \>  5 \\
0  |\> 1   \> 1  \>  1  \>  1  \>  1 \\
    --------------------------------
    \> 0   \> 1  \>  2  \>  3  \>  4 
\end{tabbing}
We will see these numbers later in the term (around lecture 16)\.  
For now, here is a formula (which we pull out of thin air), giving the 
exact value of the function on any pair of arguments:
\[
f(n,k) = \frac{(n+k)!}{n!
  k!}.
\]

Here we are using the factorial function (written ``!''):
\begin{align*}
0! &= 1\\
1! &= 1\\
n! &= n (n-1)\ldots 1
\end{align*}
Example: 
$f(3,4) = \frac{7!}{3!4!} = \frac{7.6.5.4.3.2.1}{3.2.1.4.3.2.1} = 35$. 

\begin{lemma}
$\forall n, k \in N [f(n,k) = \frac{(n+k)!}{n! k!}]$. 
\end{lemma}

\noindent We can prove this by induction\.  But there are two
variables, $n$ and $k$\.  So, we will do the proof in 2 levels\.  The
main strategy is by induction on $n$\.  And for each particular $n$,
we work by induction on $k$\.  We are doing induction inside an
induction.  \\
Let's break up the statement to make the two levels clearer:\\ 
\begin{lemma}
  $\forall n [\forall k [f(n,k) = \frac{(n+k)!}{n! k!}]]$
\end{lemma}

\noindent Define $Q(n,k)$ to be the predicate $f(n,k) =
\frac{(n+k)!}{n! k!}$.\\
$Q(n,k)$ says that the value in position $(n,k)$ is correct (satisfies
the formula). \\
Define $P(n)$ to be $\forall k [Q(n,k)]$, that is, $\forall k [f(n,k)
= \frac{(n+k)!}{n! k!}]$\.  
$P(n)$ means that all the values in row $n$ are correct\.

We use the induction pattern: 
\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}


Expanding this pattern:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 0 [P(n)]$ \\
1. (Base) $P(0)$ \\
\> 1. $\forall k [f(0,k) = \frac{(0+k)!}{0!k!}]$
   \> \> \> \> Both sides are 1 (for any $k$) \\
\> 2. QED 
   \> \> \> \> Definition of $P(0)$ \\
2. (Inductive step) $\forall n \geq 0 [P(n) \Rightarrow P(n+1)]$ \\
\> 1. Fix $n \geq 0$. \\
\> 2. Assume $P(n)$, that is, row $n$ is correct. \\
\> 3. $P(n+1)$, that is, row $n+1$ is correct.      
   \> \> \> \> ??? \\
\> 4. QED    
   \> \> \> \> Implication, UG \\
3. QED                           
\> \> \> \> \> Induction 
\end{tabbing}

Now, how to prove 3\?  It involves saying something about the whole
row $n+1$\.  
We use induction to handle all the elements in this row one at a
time\.  
Our goal 3 can be rewritten, using the definition of $P$ in terms of
$Q$\.  
Note that this is all talking just about the particular row $n+1$.

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> 3. $P(n+1)$ \\
\> \> 1. $\forall k [Q(n+1,k)]$ \\
\> \> \> 1. (Base) $Q(n+1,0)$ \\
\> \> \> 2. (Inductive step) $\forall k \geq 0 [Q(n+1,k) \Rightarrow Q(n+1,k+1)]$. \\
\> \> \> 3. QED  
         \> \> Induction \\
\> \> 2. QED
      \> \> \> Definition of $P(n+1)$
\end{tabbing}

\noindent
The base case for the inner induction follows by expanding the
definition of $Q(n+1,0)$:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> \> 1. (Base) $Q(n+1,0)$ \\
\> \> \> \> 1. $f(n+1,0) = \frac{(n+1+0)!}{(n+1)! 0!}$ 
            \> Both sides are 1 \\
\> \> \> \> 2. QED
            \> Definition of $Q(n+1)$
\end{tabbing}

\noindent
The inductive step involves a little algebra:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> \> 2. (Inductive step) $\forall k \geq 0 [Q(n+1,k) \Rightarrow Q(n+1,k+1)]$. \\
\> \> \> \> 1. Fix $k \geq 0$. \\
\> \> \> \> 2. Assume $Q(n+1,k)$. \\
\> \> \> \> 3. $Q(n+1,k+1)$ \\
\> \> \> \> \> 1. $f(n+1,k+1)= f(n,k+1) + f(n+1,k)$ \\
\> \> \> \> \> \> Definition of $f(n+1,k+1)$ \\
\> \> \> \> \> 2. $f(n+1,k) = \frac{(n+1+k)!}{(n+1)!k!}$ 
               \> Inductive hypothesis 2.3.1.2.2, \\
\> \> \> \> \> \> definition of $Q(n+1,k)$. \\
\> \> \> \> \> 3. $f(n,k+1) = \frac{(n+k+1)!}{n!(k+1)!}$ 
               \> Inductive hypothesis 2.2, \\
\> \> \> \> \> \> definition of $P(n,k+1)$. \\
\> \> \> \> \> 4. $f(n+1,k+1)=\frac{(n+k+1)!}{n!(k+1)!}+\frac{(n+1+k)!}{(n+1)!k!}
                  =\frac{(n+1+k+1)!}{(n+1)!(k+1)!}$ \\
\> \> \> \> \> \> Combining equations, algebra \\
\> \> \> \> \> 5. QED                   
               \> Definition of $Q(n+1,k+1)$ \\
\> \> \> \> 4. QED
            \> \> Induction
\end{tabbing}

The ``inner'' inductive hypothesis (the one involving $Q(n+1,k)$)
is invoked to get information about the
previous element in the same row, $n+1$\. 
The ``outer'' inductive hypothesis (the one involving $P(n,*)$),
is invoked to get information about element $k+1$ of the previous row\.
(The proof uses UI in the invocation of the outer inductive hypothesis.)

\section{Strong induction}

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)]. 
\]

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}

\section{Strong Induction Proof Examples}

\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}

\noindent In examples like these, you must be careful to consider all
the needed base (or special) cases\.  Otherwise, you might ``prove''
false theorems, e.g., that we can build all towers of size $\geq 3$:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 3 (P(n))$ \\
1. (Base) $P(3)$ \\
2. (Inductive step) $\forall n \geq 3
   [(\forall i, 3 \leq i \leq n (P(i))) \Rightarrow P(n+1)]$ \\
3. QED                        
\> \> \> \> \> Strong induction
\end{tabbing}
If we try to mimic the previous proof for this situation, we find we
can't make the jump to $4$ or $5$.

\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 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 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 first player remove 2 sticks: again, the second player sees
$4k + 1$ sticks and loses.
\end{itemize}
\end{proof}

\subsection{Fibonacci examples}

\subsubsection{Another false theorem}

Here is another false ``theorem''\.  The fallacy is like the blocks
example---we don't have enough base cases.

\begin{falsethm}
All Fibonacci numbers are even.
\end{falsethm}

We try strong induction, where $P(n)$ is defined to be ``$F_n$ is
even.'' 
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 0 [P(n)]$ \\
1. (Base) $P(0)$
\> \> \> \> \> $F_0 = 0$, which is even. \\
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 inductive step is supposed to prove that $F_{n+1}$ is even, using
the fact that all smaller Fibonacci numbers are even\.
The idea is to express $F_{n+1}$ as usual, as $F_{n-1} + F_n$\.
Then use the strong inductive hypothesis to say that $F_{n-1}$ and $F_n$
are both even\.
The sum is therefore also even\.
\\
What's the error?  We proved:
$P(0)$ \\
$P(0) \wedge P(1) \Rightarrow P(2)$ \\
$P(1) \wedge P(2) \Rightarrow P(3)$, etc. \\
But we never proved $P(1)$.

\subsubsection{A lower bound}

Here's a correct proof about Fibonacci numbers\.  It shows a lower bound
on their values.
\begin{lemma}
$\forall n \geq 2 [F_n \geq (\frac{3}{2})^{n-2}]$
\end{lemma}
\begin{proof}
Use strong induction\.
Let $P(n) = F_n \geq (\frac{3}{2})^{n-2}$
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 2 [P(n)]$\\
1. (Base) $P(2)$
\> \> \> \> \>  $F_2 = 1 = (\frac{3}{2})^0$ \\
2. (Base) $P(3)$ 
\> \> \> \> \>  $F_3 = 2 \geq (\frac{3}{2})^1$ \\
3. (Inductive step) $\forall n \geq 3 [(\forall  i, 2 \leq i \leq n (P(i))) \Rightarrow P(n+1)]$\\
\> 1. Fix $n \geq 3$ \\
\> 2. Assume $\forall  i, 2 \leq i \leq n (P(i))$ \\
\> 3. $P(n+1)$
   \> \> \> \> ??? \\
\> 4. QED
    \> \> \> \> Implication, UG \\
4. QED
\> \> \> \> \> Strong induction
\end{tabbing}

\noindent
Now in proving the ??? we are only worrying about $n \geq 3$ and we may
assume the inequality for all $i$ from $2$ up to $n$, inclusive\.
Because of the way Fibonacci numbers are defined, it turns out that the
ones we need are just $n$ and $n-1$\.
Those are in the range for which we can assume the property. 
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> 3. $P(n+1)$ \\
\> \> 1. $F_n \geq (\frac{3}{2})^{n-2}$
      \> \> \> Inductive hypothesis 3.2 \\
\> \> 2. $F_{n-1} \geq (\frac{3}{2})^{n-3}$
      \> \> \> Inductive hypothesis 3.2 \\
\> \> 3. $F_{n+1} = F_n + F_{n-1}$
      \> \> \> Definition \\
\> \> 4. $F_{n+1}\geq (\frac{3}{2})^{n-2} + (\frac{3}{2})^{n-3}$ 
      \> \> \> Plug the inequalities into the equation \\
\> \> 5. QED
      \> \> \> Algebra \\
\> \> \> 1. $\frac{3}{2} + 1 \geq (\frac{3}{2})^2$
         \> \> Arithmetic \\
\> \> \> 2. $(\frac{3}{2})^{n-2} + (\frac{3}{2})^{n-3} \geq (\frac{3}{2})^{n-1}$
         \> \> Algebra \\
\> \> \> 3. $F_{n+1} \geq (\frac{3}{2})^{n-1}$
         \> \> Algebra (3.3.4 and 3.3.5.2) \\
\> \> \> 4. QED
         \> \> Definition of $P(n+1)$ 
\end{tabbing}
\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{Tournaments}

A pure math example, interesting and slightly complicated (ordinary
and strong) inductive proofs. \\

A new Internet game company is conducting a chess tournament on the Internet.\\
Round robin, not elimination. \\
That is, everyone plays everyone exactly once. \\
Can represent the results nicely by arrows, e.g.:\\
\\
A beats B, C, D \\
B beats D \\
C beats B \\
D beats C \\
\\
Structure called a ``digraph''.  Will study them carefully soon.\\
\\
Now, the gaming company wants to use this information to make some
decisions, e.g., award first prize, rank everyone. \\
It wants to do this in such a way that its customers don't complain
about the rankings being unfair. \\
\\
There are some problems with doing this.

\subsubsection{Cycles}

Problem: The tournament graph can contain cycles. \\
Example: Above, B beats D beats C beats B. \\
\\
If there's a cycle, then any ranking method is a least a little
problematic:  someone who beat someone else would be ranked lower. \\
\\
Of course, the company has no power to avoid cycles in play
results. \\
The gaming company might hope that ``most of the time'', when there is
a cycle, it's very big (so the people involved aren't likely to
discover this). \\
However, tournaments have an unfortunate property: 
\begin{theorem}
Any tournament that contains any cycle, contains a cycle of length $3$
($3$-cycle).
\end{theorem}

That is, three players, e.g., B, C, D, above, have an ``inconsistent''
set of results. \\
\\
This can be proved by ordinary induction, where $P(n)$ is the
predicate ``Any tournament that contains an $n$-cycle contains a
$3$-cycle.''
\begin{tabbing}\\
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 3 [P(n)]$ \\
1. (Base) $P(3)$ 
\> \> \> \> \> Trivial by assumption. \\
2. (Inductive step)  $\forall n \geq 3 [P(n) \Rightarrow P(n+1)]$ \\
\> 1. Fix $n \geq 3$ \\
\> 2. Assume $P(n)$ \\
\> 3. $P(n+1)$ \\
\> \> 1. Fix $T$, a tournament, and $p_1 \rightarrow p_2 \rightarrow \ldots
\rightarrow p_{n+1} \rightarrow p_1$, an $n+1$-cycle in $T$. \\
\> \> 2. $T$ contains a $3$-cycle. 
      \> \> \> ??? \\
\> \> 3. QED
      \> \> \> Implication, UG \\
\> 4. QED
   \> \> \> \> Implication, UG \\
3. QED
\end{tabbing}
How can we find a $3$-cycle in $T$? \\
Example: [[[Draw 5-cycle]]]. \\
To get a $3$-cycle, notice that $p_1$ and $p_3$ have an arrow, one way
or the other.  \\
If from $p_3$ to $p_1$, then $p_1,p_2,p_3$ form a cycle.\\
If the other way, then can reduce the size of the cycle to omit $p_2$.
Then use induction on the smaller cycle. \\
This generalizes: 
\begin{tabbing}\\
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> 2. $T$ contains a $3$-cycle. \\
\> \> \> 1. If $p_3 \rightarrow p_1$ then $T$ contains a $3$-cycle. 
      \> \> Use $p_1 \rightarrow p_2 \rightarrow p_3 \rightarrow p_1$. \\
\> \> \> 2. If $p_1 \rightarrow p_3$ then $T$ contains a $3$-cycle. \\
\> \> \> \> 1. Assume $p_1 \rightarrow p_3$. \\
\> \> \> \> 2. $T$ contains an $n$-cycle. 
            \> Use $p_1 \rightarrow p_3 \rightarrow p_4 \rightarrow p_{n+1} \rightarrow p_1$. \\
\> \> \> \> 3. $T$ contains a $3$-cycle.
            \> By inductive hypothesis (2.2) \\
\> \> \> 3. QED
         \> \> Cases
\end{tabbing}
A detail to be careful about here: 
This argument depends on the fact that the arrow we add between $p_1$ and
$p_3$ is not already part of the original cycle. \\
That's true because we know that the original cycle had length $n+1$,
which is at least $4$. 

[[[In Fall, 00, lecture got to this point.  
The following subsection should be covered in tutorial tomorrow.  
The last subsection, on nice rankings and number of wins, 
is purely optional.]]]

\subsubsection{``Nice'' rankings}

The gaming company decides that, although they cannot avoid inconsistent
orders, they would at least like to make the ranking ``nice'',
by which they mean that if one player $p$ is ranked {\em immediately
ahead\/} of another player $q$, then $p$ must have beaten $q$. \\
(They might want to tell each player who the players were that are
ranked immediately above and below him, and don't want someone to
complain that the guy ranked above him is someone he beat.) \\
They are happy to discover: 
\begin{theorem}
Any tournament has a nice ranking.
\end{theorem}

\noindent
Example:  Above:  Can use ranking $A, D, C, B$.

Prove by strong induction, where $P(n)$ says ``any $n$-player
tournament has a nice ranking''. \\
The strategy is to ``split'' the players into those that beat and
those that lose to a particular player $x$. \\
Rank those two subsets separately, by using the inductive
hypothesis.\\
(Subtournaments) \\
Then put the rankings together. 
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 1 [P(n)]$ \\
1. (Base) $P(1)$ 
\> \> \> \> \> Obvious---just one player to be ranked. \\
2. (Inductive step)
$\forall n \geq 1 [(\forall i, 1 \leq i \leq n (P(i))) \Rightarrow P(n+1)]$ \\
\> 1. Fix $n \geq 1$ \\
\> 2. Assume $\forall i, 1 \leq i \leq n [P(i)]$. \\
\> 3. $P(n+1)$ \\
\> \> 1. Fix any $n+1$-player tournament $T$. \\
\> \> 2. $T$ has a nice ranking. \\
\> \> \> 1. Choose $x$ to be any player, $B$ the set of players that
beat $x$, and $L$ the \\
\> \> \> \> set of players that lose to $x$. \\
\> \> \> 2. $B$ has a nice ranking. 
         \> \> Inductive assumption (2.2). \\
\> \> \> 3. $L$ has a nice ranking. 
         \> \> Inductive assumption (2.2). \\
\> \> \> 4. Define a ranking $R$ of all the players by: $B$ ranking, then $x$, then $L$ ranking. \\
\> \> \> 5. $R$ is a nice ranking for $T$. \\
\> \> \> 6. QED 
         \> \> EG \\
\> \> 3. QED 
      \> \> \> UG \\
\> 4. QED
   \> \> \> \> Implication, UG \\
3. QED                        
\> \> \> \> \> Strong induction 
\end{tabbing}

\subsubsection{Nice rankings and number of wins}

For a while, the customers are happy with just nice rankings. \\
But then a game comes up where just ``niceness'' doesn't work out so well: \\
\\
Example: \\
A beats B \\
B beats C \\
C beats A,D \\
D beats A,B,E \\
E beats A,B,C 

[[[Diagram]]] 

Here, A,B,C,D,E is a nice ranking. \\
However, it's in the reverse order according to number of wins. \\
Bad. \\
Now it occurs to the company that it would be nice if the rankings could
also be consistent with number of wins. \\
It turns out this is not possible (in combination with ``niceness''). 
%
%Example: 6 players \\
%A beats C,D,E,F (4 wins) \\
%B beats A,E,F (3 wins) \\
%C beats B,F (2 wins) \\
%D beats C,B (2 wins) \\
%E beats C,D (2 wins) \\
%F beats D,E (2 wins) \\
%
%(Draw)
%
%Ordering consistently with number of wins would mean $A$ would have to
%be ranked immediately ahead of $B$. \\
%But $B$ beats $A$, violating niceness. \\\
%
So then they decide they will be happy to settle for a nice ranking in
which the highest ranked player has the largest number of wins (can be
tied). \\
This would rule out the bad example above. \\
\\
Turns out this is possible: \\
In fact, in the event of a tie, the company has the option of choosing
which best player is ranked first: \\
\\
Define $P(n)$: For any $n$-player tournament $T$ and any $z$ that has
the largest number of wins in $T$, there exists a nice ranking
with $z$ ranked first. 
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 1 [P(n)]$ 
\end{tabbing}
This can be proved by induction, but the inductive step is more
complicated than in the previous proof. \\
\\
First proof attempt: \\
Try a proof like the previous one, this time splitting on some $x$
that loses to $z$. \\
Now split all-but-$x$ into $B$ and $L$ as before, based on their
records with respect to $x$. \\
We know that $z$ is in $B$, because it beats $x$. \\
Now try to use the inductive hypothesis to rank $B$ while keeping $z$
first, and to rank $L$. \\
Then combine as before. \\
\\
Sounds plausible---but wrong: \\
Applying the inductive hypothesis requires that $z$ have the best
won-lost record in the ``subtournament'' involving just the $B$
elements. \\
But it might not: \\
\\
Example: \\
Players z, y, x, and a lot of p's \\
z and y beat x \\
x beats all of the p's \\
y beats z \\
z beats all the p's \\
All the p's beat B \\
Doesn't matter what happens among the p's. 

[[[diagram]]] 

$z$ has the best record overall, but in the two-player subtournament consisting
of guys that beat $x$, $z$ is worse than $y$. \\
\\
Try again: \\
It turns out that a correct proof can be given using ordinary (not
strong) induction: \\
Recall $P(n)$: For any $n$-player tournament $T$ and any $z$ that has
the largest number of wins in $T$, there exists a nice ranking
with $z$ ranked first. 
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 1 (P(n))$ \\
1. (Base) $P(1)$ 
\> \> \> \> \> Only one possibility. \\
2. (Inductive step) $\forall n \geq 1 [P(n) \Rightarrow P(n+1)]$ \\
\> 1. Fix $n \geq 1$. \\
\> 2. Assume $P(n)$. \\
\> 3. $P(n+1)$. \\
\> \> 1. Fix $T$, an $n+1$-player tournament, and $z$, a player with the most wins. \\
\> \> 2. $\exists$ a nice ranking of $T$ with $z$ first. 
      \> \> \> ??? \\
\> \> 3. QED 
      \> \> \> UG \\
\> 4. QED   
   \> \> \> \> Implication, UG \\
3. QED                        
\> \> \> \> \> Induction 
\end{tabbing}
The key step will break down into cases, based on whether or not $z$
lost any matches.  \\
The case where $z$ won everything is easy; the other case is tricky:
Here's the easy case:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> 2. $\exists$ a nice ranking of $T$ with $z$ first. \\
\> \> \> 1. If $z$ is undefeated in $T$ then $\exists$ a nice
ranking of $T$ with $z$ first. \\
\> \> \> \> 1. Assume $z$ is undefeated in $T$. \\
\> \> \> \> 2. Choose $R$ to be a nice ranking of all-but-$z$. \\
\> \> \> \> \> Previous theorem says this exists, EI \\
\> \> \> \> 3. $z$ then $R$ is a nice ranking of $T$. \\
\> \> \> \> 4. $\exists$ a nice ranking of $T$ with $z$ first. \\
\> \> \> \> \> EG \\
\> \> \> \> 5. QED 
            \> Implication \\
\> \> \> 2. If $z$ is defeated by someone then $\exists$ a nice
ranking of $T$ with $z$ first. \\
\> \> \> \> \> ??? \\
\> \> \> 3. QED 
         \> \> Cases
\end{tabbing}

And the tricky case:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> \> 2. If $z$ is defeated by someone then $\exists$ a nice
ranking of $T$ with $z$ first. \\
\> \> \> \> 1. Assume $z$ is defeated by someone. \\
\> \> \> \> 2. Choose $x$ to be someone who defeated $z$. \\
\> \> \> \> 3. $z$ has the best record in the subtournament involving all-but-$x$.\\
\> \> \> \> \> $z$ had the best record in $T$, \\
\> \> \> \> \> no wins are removed. \\
\> \> \> \> 4. $\exists$ ranking of subtournament having $z$ first. \\
\> \> \> \> \> Inductive hypothesis, $z$ has best record. \\
\> \> \> \> 5. Choose $R$ to be a ranking of all-but-$x$ having $z$ first. \\
\> \> \> \> \> EI \\
\> \> \> \> 6. In $T$, $x$ is defeated by someone. 
            \> $z$ was defeated, and $x$'s record in $T$ can't \\
\> \> \> \> \> be better than $z$'s. \\
\> \> \> \> 7. Define ranking $S$ to be $R$, with $x$ inserted right after the lowest-ranked player \\
\> \> \> \> that beats $x$. \\
\> \> \> \> 8. $S$ is a nice ranking of $T$. \\
\> \> \> \> \> $R$ is nice, $x$ is beaten by the player ranked \\
\> \> \> \> \> just above it and beats all ranked below it. \\
\> \> \> \> 9. $z$ is first in $S$. 
            \> $z$ is first in $R$, and $x$ is not inserted \\
\> \> \> \> \> at the top. \\
\> \> \> \> 10. $\exists$ a nice ranking of $T$ with $z$ first. \\
\> \> \> \> \> $S$ works, EG \\
\> \> \> \> QED 
            \> Implication \\
\end{tabbing}

\end{document}

% LocalWords:  HW pset XXX XXXXXXXXXXXXXXXXXXXX UG CS poly def UI ponens
