\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$.
