
\section{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.
