\documentclass[11pt,twoside]{article}
\usepackage{macros-course-lectures}
\usepackage{graphics}
\renewcommand{\thepage}{\arabic{page}}

%\makeslides

\begin{document}

\onlystudents

\lecture{notes3}{Proof by Induction}{February 13, 2001}

\forlecture{Print/lecture on definitions}

\forlecture{Get feedback on pace/difficulty of first week's material and HW.

\noindent
Topics for today:
\begin{itemize}
\item
Induction plus examples
\item
Strong induction plus examples
\item
Fallacies
\end{itemize}

}



\reading{Velleman 6.1--6.2; Rosen 3.2}


\section{Mathematical induction}

Induction is the most important proof method in computer science\.  
Suppose you want to prove that $P(n)$ is true for
all $n \in N$\.
You can prove it individually for $0,1,\ldots$\.  
But that has to stop sometime\.
The proof method of mathematical induction says that you just need
to prove it for $0$, then prove ``if it's true for $n$ then it's true
for $n+1$''\.

Why does this prove it for all $n \in \naturals$\?  
It may seem obvious$\ldots$consider falling dominoes$\ldots$\.
Actually, it's part of how $\naturals$ is defined\.
It's usually taken as an assumption (axiom) about $\naturals$: \\ 

{\bf Induction axiom:} $[P(0) \wedge \forall n \geq 0 (P(n) \Rightarrow
P(n+1))] \Rightarrow \forall n (P(n))$. \\
Alternatively, you can see it as a deduction rule\.  The pattern is:

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
To prove: $\forall n \geq 0 (P(n))$ \\
It's enough to show:\\
1. (Base) $P(0)$ \\
2. (Inductive step) $\forall n \geq 0 (P(n) \Rightarrow P(n+1))$
\end{tabbing}

There is a variant if you only want to prove it for $n \ge k$:

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
To prove: $\forall n \geq k (P(n))$\\
It's enough to show:\\
1. (Base) $P(k)$ \\
2. (Inductive step) $\forall n \geq k (P(n) \Rightarrow P(n+1))$
\end{tabbing}

\section{Inductive proof examples}

\subsection{Sum of Series}

This is the canonical first example for induction:

\begin{lemma}
$\forall n \geq 0 (1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2})$ 
\end{lemma}

\noindent Alternatively (and this is better), we can write the LHS in
closed form:
\[ \sum_{i=1}^n i \mbox{ or } \sum_{1 \leq i \leq n} i
\]
Thus, we want to prove: 
\[
\forall n \geq 0 (\sum_{i=1}^n i = \frac{n(n+1)}{2})
\]
Let's stop and be sure we know what this summation means\.  First
check boundary cases (always a good idea to see if you understand a
definition).

\begin{itemize}
\item If $n = 1$, then the sum $1 + 2 + 3 + \ldots + n = 1$.  The sum
  has one term only.  The appearance of $2$, $3$, and $n$ is
  misleading!
\item 
If $n = 0$, then $1 + 2 + 3 + \ldots + n = 0$. 
There are no terms present in the summation.
\end{itemize}

\noindent
Now, the induction pattern says:
\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}

\noindent
Here, we define $P(n)$ to be the predicate $\sum_{i=1}^n i =
\frac{n(n+1)}{2}$\.
In other words: 

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 0 (\sum_{i=1}^n i = \frac{n(n+1)}{2})$.\\
1. (Base) $\sum_{i=1}^0 i = \frac{0(0+1)}{2}$. \\
2. (Inductive step) 
   $\forall n \geq 0 (\sum_{i=1}^n i = \frac{n(n+1)}{2} \Rightarrow
                      \sum_{i=1}^{n+1} i = \frac{(n+1)(n+2)}{2})$ \\
3. QED                              
\> \> \> \> \> Induction 
\end{tabbing}
The two steps of the proof are called the {\em base\/} and the {\em
induction step\/}. \\
Usually, the base step is pretty easy to check, but the inductive step
can involve some work and creativity. 

\noindent
Whether you give a structured or paragraph style proof, the proof must
contain, clearly, all of the following:
\begin{enumerate}
\item 
A statement that the proof is by induction.
\item 
The definition of the predicate $P(n)$.
\item 
The proof of the base step, $P(0)$ (or $P(k)$, if we're starting from
some other value $k$).
\item 
The proof of the inductive step,
$\forall n \geq 0 (P(n) \Rightarrow P(n+1)$
\end{enumerate}

\noindent
To finish this example: \\
Base:  Easy by definition and arithmetic.
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
1. (Base) $\sum_{i=1}^0 i = \frac{0(0+1)}{2}$ ($P(0)$) \\
\> 1. $\sum_{i=1}^0 i = 0$
   \> \> \> \> Definition of summation with no terms \\
\> 2. $\frac{0(0+1)}{2} = 0$
   \> \> \> \> Arithmetic \\
\> 3. QED
   \> \> \> \> By 1.1 and 1.2.
\end{tabbing}
\noindent
The inductive step uses basic logic (UG and implication)\.
What's left is the job of showing that, assuming $P(n)$, we can prove
$P(n+1)$. 

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
2. (Inductive step) 
   $\forall n \geq 0 (\sum_{i=1}^n i = \frac{n(n+1)}{2} \Rightarrow
                      \sum_{i=1}^{n+1} i = \frac{(n+1)(n+2)}{2})$ \\
\> 1. Fix $n \geq 0$. \\
\> 2. $\sum_{i=1}^n i = \frac{n(n+1)}{2} \Rightarrow 
       \sum_{i=1}^{n+1}i = \frac{(n+1)(n+2)}{2}$ \\
\> \> 1. Assume $\sum_{i=1}^n i = \frac{n(n+1)}{2}$ \\
\> \> 2. $\sum_{i=1}^{n+1}i= \frac{(n+1)(n+2)}{2}$ 
      \> \> \> ??? \\
\> \> 3. QED   
      \> \> \> Implication \\
\> 3. QED
   \> \> \> \> UG 
\end{tabbing}

\noindent
The important job is step 2, showing $P(n+1)$\.
To do this, we just write out the equation we want to show (for
$n+1$), and play around with both sides to try to make them equal\.
Remember that we are allowed to use the assumption $P(n)$, which is
the corresponding equation for $n$\.
So while we are manipulating the equation for $n+1$, we look for a
place to plug in the information for $n$\.

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> 2. $\sum_{i=1}^{n+1}i = \frac{(n+1)(n+2)}{2}$ \\
\> \> \> 1. $\sum_{i=1}^{n+1}i = (\sum_{i=1}^{n}i)  + (n+1)$ 
         \> \> Summation has one extra term. \\
\> \> \> 2. $(\sum_{i=1}^{n}i) + (n+1) = \frac{n(n+1)}{2}+ n+1$
         \> \> Inductive hypothesis $P(n)$ (2.2.1) \\
\> \> \> 3. $\frac{n(n+1)}{2} + n+1 = \frac{(n+1)(n+2)}{2}$
         \> \> Algebra \\
\> \> \> 4. QED 
         \> \> Combining the previous 3 equations.
\end{tabbing}

\noindent This worked out nicely because the left hand side (LHS) of
the $n+1$ equation was easily expressible in terms of the $n$
equation\.  Sometimes we'll have to work harder\.  Also, here the
choice of $P(n)$ came directly out of the theorem statement\.
Sometimes it isn't so obvious.

Also in this example, note that the inductive technique did not help
us to come up with the correct expression $\frac{n(n+1)}{2}$ for the
summation, but only to prove that it is correct\.  We'll see how to
come up with such sums when we get to the analysis methods part of
this course.

\subsection{Remarks}

Note that many proofs that say ``and so on'' are likely to be
an induction in disguise (and you need to remove that disguise to make
the proof formal).

Note also that an induction is {\bf not} a circular argument.  Using
$P(n)$ to prove $P(n)$ would be circular, but using $P(n)$ to prove
$P(n+1)$ is fine because it eventually unravels down to $P(0)$ which
has been proved by other means.

\forstudents[Brief discussion of divisibility]{
\subsection{Divisibility}

\begin{definition}
Given two integers $x$ and $y$, we say $x$ \emph{divides} $y$, and
write $x \mid y$, if there is no remainder on division of $y$ by $x$.
That is, $y = cx$ for some integer $c$.
\end{definition}

\begin{lemma}
$\forall n \in N, n \geq 0 (6 | n^3 - n)$
\end{lemma}
We will prove this by induction on $n$, with base case $0$\.  Thus,
$P(n)$ is the predicate $6 | n^3 - n$\.  Base $P(0)$ looks obvious,
because $6 | 0$ by definition\.  How about the inductive step?
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \in N, n \geq 0 (6 | n^3 - n)$ \\
1. (Base) $6 | 0^3 - 0$ \\
2. (Inductive step) $\forall n \geq 0 (6 | n^3 - n \Rightarrow 6 | 
(n+1)^3 - (n+1))$ \\
\> 1. Fix $n \geq 0$.\\
\> 2. Assume $6 | n^3 - n$ \\
\> 3. $6 | (n+1)^3 - (n+1)$
   \> \> \> \> ??? \\
\> 4. QED     
   \> \> \> \> Implication, UG (condensing two steps) \\
3. QED 
\> \> \> \> \> Induction 
\end{tabbing}

\noindent Now, how to get from 2.2 to 2.3\?  Since both the
expressions have high-order $n^3$ terms, we can try subtracting\.  The
difference is $((n+1)^3 - (n+1)) - (n^3 - n)$, which works out to
$3n^2 + 3n$\.  If we know that $6$ divides this difference, and we are
assuming that $6$ divides $n^3 - n$, it follows that $6 | (n+1)^3 -
(n+1)$, which is the sum\.  That's what we needed\.

So the problem reduces to showing $6 | 3n^2 + 3n$\.  This factors into
$3(n^2 + n)$\.  But we know that $n^2 + n$ is even, that is, $2 | n^2
+ n$\.  If we multiply the expression by $3$, then $6$ certainly
divides the result\.

This discussion contained all the ideas needed for the proof\.  Now
we will put it all together in a complete proof\.

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \in N, n \geq 0 (6 | n^3 - n)$ \\
1. (Base) $6 | 0^3 - 0$ \\
2. (Inductive step) $\forall n \geq 0 (6 | n^3 - n \Rightarrow 6 |
(n+1)^3 - (n+1))$ \\
\> 1. Fix $n \geq 0$. \\
\> 2. Assume $6 | n^3 - n$ \\
\> 3. $6 | (n+1)^3 - (n+1)$ \\
\> \> 1. $(n+1)^3 - (n+1) = n^3 - n  + 3(n^2 + n)$
      \> \> \> Algebra \\
\> \> 2. $n^2 + n$ is even   
      \> \> \> Proved this earlier today \\
\> \> 3. $2 | n^2 + n$  
      \> \> \> Definition of $|$ \\
\> \> 4. $6 | 3(n^2 + n)$ 
      \> \> \> Multiplying both sides by $3$ \\
\> \> \> \> \> (basic properties of $N$)\\
\> \> 5. $6 | (n^3 - n)  + 3(n^2 + n)$
      \> \> \> Divides both terms (2.2, 2.3.4), \\
\> \> \> \> \> so divides sum. \\
\> \> 6. QED 
      \> \> \> 2.3.1, 2.3.5 \\
\> 4. QED \\
3. QED \\
\end{tabbing}
}

\subsection{A string example}

\begin{lemma}
There are exactly $2^n$ different length $n$ strings of $0$s and $1$s.
\end{lemma}
\begin{proof}
Let $P(n)$ be the given statement.

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 0 (P(n))$ \\
1. (Base) $P(0)$ 
\> \> \> \> \> There's exactly one empty string \\
\> \> \> \> \> of $0$s and $1$s. \\
2. (Inductive step) $\forall n \geq 0 (P(n) \Rightarrow P(n+1))$ \\
\> 1. Fix $n \geq 0$. \\
\> 2. Assume $P(n)$, that is, there are $2^n$ length $n$ strings. \\
\> 3. $P(n+1)$, that is, there are $2^{n+1}$ length $n+1$ strings. \\
\> \> \> \> \> Every string of length $n$ can have either \\
\> \> \> \> \> a $0$ or a $1$ attached at the end.  \\
\> 4. QED   
   \> \> \> \> Implication, UG \\
3. QED                        
\> \> \> \> \> Induction 
\end{tabbing}
\end{proof}

\subsection{Geometry}

\begin{definition}
  A convex polygon is a polygon such that any straight line between
  any two vertices doesn't leave the polygon.
\end{definition}
\forlecture{

Draw one.}

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
$P(n)$: The sum of the interior angles in any $n$-sided
convex polygon is exactly $(n-2) \cdot 180$ degrees\.
\\
Prove: $\forall n \geq 3$ (The sum of the interior angles in any $n$-sided
convex polygon is exactly \\
$(n-2) 180$ degrees.) \\
1. (Base) $P(3)$: Sum of angles in any triangle is $180$.
\> \> \> \> \> Basic fact from geometry \\
2. (Inductive step) $\forall n \geq 3 (P(n) \Rightarrow P(n+1))$ \\
\> 1. Fix $n \geq 3$. \\
\> 2. Assume sum of angles of any $n$-sided convex polygon is $(n-2) 180$. \\
\> 3. Sum of angles of any $n+1$-sided convex polygon is $(n-1) 180$. \\
\> \> 1. Fix any $n+1$-vertex convex polygon $X$, say with vertices
$x_1,x_2,\ldots,x_{n+1}$. \\
\> \> 2. Let $Y$ be the polygon with vertices $x_1,x_2,\ldots,x_n$
(cuts out one vertex). \\
\> \> 3. $Y$ is a convex polygon with at least 3 vertices. \\
\> \> 4. Sum of interior angles of $Y$ is $(n-2)180$. 
      \> \> \> Inductive hypothesis (2.2) \\
\> \> 5. Sum of interior angles of triangle $T = x_n, x_{n+1}, x_1$ is
$180$. \\
\> \> \> \> \> Basic fact from geometry \\
\> \> 6. Sum of angles in $X$ = sum in $Y$ + sum in $T$, $= (n-2)180 +
180 = (n-1)180$. \\
\> \> \> \> \> Basic geometry, arithmetic. \\
\> \> 7. QED
      \> \> \> UG \\
\> 4. QED  
   \> \> \> \> Implication, UG \\
3. QED 
\> \> \> \> \> Induction
\end{tabbing}

\noindent
UG is used to conclude something about all polygons from what we showed
for any particular polygon, and to conclude something about all $n$ from
what we showed about any particular $n$.

\section{Strengthening the Hypothesis: Tiling}

Our next proof illustrates some new ideas:
\begin{itemize}
\item Sometimes you need to strengthen inductive hypothesis in order to
  prove it.
\item Sometimes induction helps finding a construction, not just do a
  proof.
\end{itemize}

The new CS building currently under construction (on Vassar Street,
next to the pool) will cost about \$140 million\.  
Money has come from many donors, including Bill Gates\.
Donors get something in return, e.g., something named after them\.
What Bill G. wants is one of the buildings named after him, plus a
statue of himself in the middle of the courtyard\.

The planned courtyard consists of $2^n \times 2^n$ squares, for some
$n \geq 1$\.  (We don't yet know how big $n$ is)\.  The architect,
Frank Gehry, wants to cover most of this with L-shaped tiles, each
covering three squares\.  But one of the four center squares will be
left empty, for the statue\.  Can this be done?  If so, how?
(We want a general solution, for all values of $n$)\.  

Example: $n = 2$
\begin{figure}
\begin{picture}(100,100)

\put(0,0){\line(1,0){100}}
\put(25,25){\line(1,0){50}}
\put(25,75){\line(1,0){50}}
\put(0,100){\line(1,0){100}}

\put(0,50){\line(1,0){25}}
\put(75,50){\line(1,0){25}}

\put(0,0){\line(0,1){100}}
\put(25,25){\line(0,1){50}}
\put(75,25){\line(0,1){50}}
\put(100,0){\line(0,1){100}}

\put(50,50){\line(0,1){25}}
\put(50,50){\line(1,0){25}}

\put(50,0,){\line(0,1){25}}
\put(50,75){\line(0,1){25}}

\put(50,50){\framebox(25,25){B}}

\end{picture}
\caption{A legal tiling of a 4x4 courtyard.  The B marks Bill.}
\end{figure}

Can we prove what we want by induction\?  For $P(n)$, let's try: \\ 
For any $2^n \times 2^n$ courtyard, and any particular central square,
$\exists$ a tiling of the courtyard with exactly that square left
untiled.

\begin{proof}
  {\em (doomed attempt)} In the base case: $n = 1$, we can use just
  one tile\.  In the inductive step, we try to produce a tiling of a
  $2^{n+1} \times 2^{n+1}$ courtyard with one center square blank\.
  We can assume tilings of any $2^n \times 2^n$ courtyard with any
  center square blank\.  We might think of subdividing into four $2^n
  \times 2^n$ sub-courtyards\.  But it doesn't seem to help to be able
  to tile those with centers left open...
\end{proof}

Here we've hit the first case where just trying to prove the statement
directly by induction doesn't work\.
The solution may be surprising: \newl\
Prove a {\em stronger\/} theorem that implies the one we want\. \\
But isn't that harder? 
Actually, strengthening a statement to be proved by induction often
makes the proof {\em easier\/}\.  The reason is that, although we have
to prove a stronger $P(n+1)$, we also can rely on a stronger $P(n)$\.

Here, let's redefine $P(n)$ to be the predicate that says, for {\em every\/}
square in a $2^n \times 2^n$ courtyard, we can tile the rest of the 
courtyard, with that square left blank\.
Stronger\.
But now $P(n) \Rightarrow P(n+1)$ is easier\.
And the theorem we wanted originally is just a special case.

\begin{proof}
  Induction\.  The base, $P(1)$, is as before\.  For the inductive
  step, $n \geq 1$, start with an arbitrary $2^{n+1} \times 2^{n+1}$
  courtyard with an arbitrary square to leave blank\.  Let's try to
  tile this, assuming tilings of any $2^n \times 2^n$ courtyard with
  {\em any\/} square blank\.

  Again, divide the $2^{n+1} \times 2^{n+1}$ courtyard into four $2^n
  \times 2^n$ quadrants\.  One will contain the square that must be
  left blank; it can be tiled by inductive hypothesis\. \\
  Next, put one tile in the center, covering one square in each of the
  other 3 quadrants\.  Now use the inductive hypothesis three more
  times to tile the rest of the 3 quadrants.
\end{proof}

Make sure you understand the logical structure of this proof\.
This proof provides a tiling method, not just existence proof\. 
And it gives a stronger result than we originally were looking for.

This proof not only showed the existence of a tiling---it actually gave a
recipe for {\em producing\/} one\.
For 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. (See Figure \ref{tiling2})

\begin{figure}[h]
\begin{center}
\scalebox{0.5}{\includegraphics{figures/tilings}}
\end{center}
\caption{A valid tiling for an 8x8 square leaving the upper right corner empty}\label{tiling2}
\end{figure}




%[[[Diagram]]]

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

The inductive proof here yields a recursive tiling algorithm.


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


\subsection{Fallacies}

There are several common mistakes made in inductive proofs.


One common problem is failure to consider all the needed base (or
special) cases\.  This may let you ``prove'' false theorems, e.g.,
that we can build all towers of size $\geq 3$:
\begin{structproof}
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{structproof}
If we try to mimic the previous proof for this situation, we find we
can't make the jump to $4$ or $5$.



The following is a famous one:

\begin{falsethm}
All horses are the same color.
\end{falsethm}

\begin{proof}
Let $P(n)$ be the proposition that all horses in any set of $n$ horses
are the same color. \\
Clearly, $P(1)$ is true. \\
Now assume that $P(n)$ is true. \\
Consider any $n+1$ horses; number these as horses $1,2,3,\ldots,n+1$. \\
The first $n$ of these horses are the same color,
and the last $n$ are also the same color. \\
Since the set of the first $n$ horses and the set of the last $n$
horses overlap, all of the $n+1$ horses are the same color. \\
This shows that $P(n+1)$ is true and finishes the proof by induction.
\end{proof}

\forlecture{
This proof is wrong because the inductive step does not work for $n = 1$, 
i.e. the truth of $P(1)$ does not imply the truth of $P(2)$.
}

Another common mistake is using an inductive hypothesis that is just
too weak. \\
E.g., in the tiling example, the hypothesis that you can tile with any
center square missing. \\
Another example of this sort is the following variant on the triangle
angle-sum example.  

\begin{falsethm}
All {\em regular} convex polygons with $n$ sides have angles summing to
$(n-2)180^\circ$.
\end{falsethm}

\begin{proof} 
False proof. \\
The proof is by induction. \\
Let $P(n)$ be the proposition that all regular convex polygons with
$n$ sides have angles summing to $(n-2)180^\circ$.\\
{\em BASE CASE:} $P(3)$ is true since an equilateral triangle has  angles summing to
$(3-2)180^\circ$.\\
{\em INDUCTIVE STEP:} Assume $P(k)$ to be true, for all $k \leq n$. Consider a regular convex polygon with $n+1$ sides. Consider three vertices $A,B,C$ that appear consecutively on the
boundary of the polygon.  Draw a line $AC$.  This produces a triangle
$ABC$ and a polygon with $n$ vertices (we've removed $B$).  By 
lemma 2, the smaller polygon is convex and thus, by the
induction hypothesis, contains $(n-2)180^\circ$.  We now add in the
$180^\circ$ contained in the angles of $ABC$ to find that the total
angle sum in the $(n+1)$-vertex polygon is $(n-2)180^\circ+180^\circ =
((n+1)-2)180^\circ$, which proves $P(n+1)$.

This completes the inductive step and hence $P(n)$ is true for all nonnegative
integers $n$.
\end{proof}

The above proof is wrong because the inductive hypothesis has been
invoked wrongly. \\
The smaller polygon created by line $AC$ is not {\em regular}. \\
But this is almost the same proof as our correct one.

\section{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 \\
\\
See Figure \ref{tournamentintro}.
\begin{figure}[h]
\begin{center}
\scalebox{0.4}{\rotatebox{270}{\includegraphics{figures/tournamentintro}}}
\end{center}
\caption{A digraph representing the outcome of a tournament}\label{tournamentintro}
\end{figure}


Structure called a ``digraph''.  We'll 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.

\subsection{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:

\begin{figure}[h]
\begin{center}
\scalebox{0.32}{\includegraphics{figures/tournament}}
\end{center}
\caption{A tournament graph containing a 5-cycle}
\end{figure}


 %[[[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$. 

\subsection{``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}

\forstudents{
\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: (See Figure \ref{outcome1}) \\
A beats B \\
B beats C \\
C beats A,D \\
D beats A,B,E \\
E beats A,B,C 


%[[[Diagram]]] 
\begin{figure}[h]
\begin{center}
\scalebox{0.4}{\includegraphics{figures/whobeatswhom}}
\end{center}
\caption{Outcome of the game}\label{outcome1}
\end{figure}



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: (See Figure \ref{outcome2})\\
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 y \\
Doesn't matter what happens among the p's. 
\begin{figure}[h]
\begin{center}
\scalebox{0.45}{\includegraphics{figures/outcome2}}
\end{center}
\caption{Outcome of the game}\label{outcome2}
\end{figure}

%[[[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}
\section{Induction, Strong Induction, and Well-Ordering}

\subsection{Induction vs. strong induction}

Strong induction looks like a more powerful proof method than ordinary
induction, because it allows more information to be assumed in the
inductive step\.
But it's not really stronger---anything that can be proved with strong
induction can also be proved with ordinary induction\. 
Here's an example.

Recall the proof that every natural number $\geq 2$ can be written as
product of primes (factored into primes)\.
We used strong induction, where $P(n)$ was the predicate ``$n$ can be
factored into primes''\. 
The inductive step involved writing $n+1 = a b$, and using $P(a)$ and
$P(b)$ to get factorizations for $a$ and $b$, then multiplying
them\. 

Now we'll change this to an ordinary inductive proof\.
Define a new predicate $Q(n)$ to be $\forall i, 2 \leq i \leq n$
($i$ can be factored)\.  We'll
prove $Q(n)$ by ordinary induction: \\
\\
$Q(2)$:  Same as $P(2)$, use same proof. \\
\\
$Q(n) \Rightarrow Q(n+1)$: \\
Our goal is now to show: $\forall i, 2 \leq i \leq n+1$ ($i$ can be
factored). \\
What we can assume is: $\forall i, 2 \leq i \leq n$ ($i$ can be factored). \\
\\
This means that all that needs to be shown is that $n+1$ can be factored
(the others are already assumed)\. 
And we can assume factorizations of all smaller numbers\. 
So the old strong induction step can be used to show this\. 
\\
This idea is quite general\.
We  can always convert a strong inductive proof of $\forall n \geq k
(P(n))$ to an ordinary inductive proof\. 
Just define $Q(n)$ to be $\forall i, k \leq i \leq n (P(i))$, that is,
$P(k) \wedge P(k+1) \wedge \cdots \wedge P(n)$.

\begin{description}
\item[Base case:]
Show $Q(k)$, same as $P(k)$, which has already been shown as
part of the strong induction proof. 
\item[Inductive step:]
Show $Q(n) \Rightarrow Q(n+1)$, in other words,
$P(k) \wedge P(k+1) \wedge \cdots \wedge P(n) \Rightarrow
 P(k) \wedge P(k+1) \wedge \cdots \wedge P(n) \wedge P(n+1)$. 

This really amounts to showing
$P(k) \wedge P(k+1) \wedge \cdots \wedge P(n) \Rightarrow P(n+1)$\. 
But this has already been shown in the strong induction proof.
\end{description}

Of course, any ordinary inductive proof {\bf is} a strong induction
proof has well\.  We are allowed to assume $P(1),\ldots,P(n)$ to prove
$P(n+1)$, but all we actually use is $P(n)$.

Induction and strong induction are said to be ``equivalent'' proof
rules, in that each can prove the same things (in the context of some
standard number axioms and logical deduction rules). 
}

\subsection{Well-ordering}


There is another variation of induction that is sometimes useful:
well-ordering.  The well-ordering axiom looks nothing like the
induction axiom:

\begin{axiom*}
Every nonempty subset $S \subseteq \naturals$ has a smallest element.
\end{axiom*}

The well-ordering axiom is often called the well-ordering principle\.
It may seem obvious and useless!

As for obvious, note that this axiom would be false if the set of
natural number, ${\cal N}$, were replaced by, say, the set of rational
numbers\.  The subset $S$ consisting of positive rational numbers has
no smallest element.

As for useless, it turns out the well-ordering is just as powerful as
our very best weapon, strong induction!

For example: we can prove the theorem about $3$-cycles using
well-ordering instead of induction. 

\begin{theorem}
Any tournament that contains a cycle contains a $3$-cycle.
\end{theorem}
\begin{proof}
Assume tournament $T$ contains a cycle\.
Let $n$ be the smallest cycle length (there is some smallest, by
well-ordering)\. 
$n$ must be at least $3$\.  
If it's $3$, then we're done\. 
So suppose $n \ge 4$\.  Consider a cycle with this length\.
Now consider $p_1$ and $p_3$ as before\. 
Whichever way the arrow goes, we can use it in constructing a shorter
cycle in $T$ (as we did before)\. 
This is a contradiction, since we assumed that $n$ is the smallest
cycle length\.  Since we got a contradiction to our assumption that
$n\ge 4$, we must have $n=3$ as claimed.
\end{proof}

This proof is really very similar to the other one\.  In general,
well-ordering is equivalent to induction (and strong induction), in
that they can be used to prove the same theorems.  Again the
transformation is standard\.  Given an induction proof for proposition
$P(n)$, we can build a well ordering proof as follows\.  Suppose for
the purpose of contradiction that $P(n)$ is \emph{not} true for every
$n$\.  That means it is false for some $n$\.  So consider the set of
elements $n$ for which $P(n)$ is false\.  We've just assumed this set
is nonempty\.  So by well ordering it has a smallest element, say
$k$\.  This means $P(k-1)$ is true (else $k-1$ would be in our set)\.
But in our original inductive proof for $P(n)$, we showed that $P(k-1)
\implies P(k)$\ (this is the inductive step).  So $P(k)$ must be
true\.  This is a contradiction to our choice of $k$, which shows that
our original assumption (that $P(n)$ is false for some $n$) is false.

Mathematicians like well-ordering, because it is often ``prettier''
(fewer symbols) than an induction proof\.  On the other hand, as it
often involves proof by contradiction, well ordering is easier to get
confused about.

As we mentioned above, well ordering is exactly as powerful as
induction\.  To see this, consider some predicate $P(n)$ for which we
have proven the necessary pieces of an inductive proof: $P(0)$, and
$(\forall n \in \naturals) P(n) \implies P(n+1)$\.  Without using the
induction rule, we will use well ordering to deduce that $(\forall n)
P(n)$.

We use a proof by contradiction\.  Suppose that $(\forall n )P(n)$ is
false\.  In other words, $(\exists n) \neg P(n)$.  Let $S$ be the set
\[
S= \{n \mid \neg P(n)\}.
\]
By the existence claim above, $S$ is nonempty\.  By well ordering, $S$
contains a least element, say $n_0$.  By definition of $S$, $\neg
P(n_0)$ holds.  We now consider two cases\.  If $n_0=0$, we have a
contradiction since we know $P(0)$ is true\.  On the other hand, if
$n_0 \ne 0$, consider $n_0-1$, another natural number\.  Since $n_0-1
< n_0$, we know $n_0-1 \notin S$ (since $n_0$ is the smallest element
of $S$)\.  It follows that $P(n_0-1)$ is true\.  But we know that
$P(n_0-1) \implies P(n_0)$\.  It follows that $P(n_0)$ must be true
(modus ponens)\.  So $n_0 \notin S$.  This is a contradiction\.

We have shown that either case on $n_0$ is a contradiction, so our
assumption (that $S$ is nonempty) must be false\.  We deduce $(\forall
n)P(n)$ is true.

\end{document}

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