% 35 copies

\documentclass[12pt,twoside]{article}
\usepackage{psfig}
\input{macros-course}

\newenvironment{claim}{\ \vspace{0.2cm} \\ {\bf Claim: \ }}{}

\begin{document}
\handout{proofs_ind}{Induction Proofs:  Valid or Invalid?}{August 9, 2004}

\noindent Determine whether the following proofs are valid.  If a
proof is wrong, pinpoint the precise error.  If it is correct, justify
each step.

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}

% Need multiple base cases.

\begin{claim}
For all real $x \neq 0$ and all natural numbers $n$, we have $x^n = 1$.
\end{claim}

\begin{proof}
The proof is by strong induction on $n$ with the hypothesis that $x^n
= 1$ for all real $x \neq 0$.  For the base case, observe that if $x
\neq 0$, we have $x^0 = 1$ by definition.

In the inductive step, assume that $x^0 = \ldots = x^n = 1$, and we
shall prove that that $x^{n+1} = 1$.  We reason as follows:

\begin{eqnarray*}
x^{n+1}	& = &	\frac{x^n \cdot x^n}{x^{n-1}} \\
	& = &	\frac{1 \cdot 1}{1} \\
	& = &	1
\end{eqnarray*}
\end{proof}

\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}

% This proof relies on the misleading nature of ... notation to
% obscure an error in a degenerate case of the induction argument,
% namely P(1) => P(2).

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

\begin{proof}
We shall prove that in every finite, nonempty set of horses, all are
the same color.  Since the set of all horses is finite, the claim
follows.

The proof is by induction.  The induction hypothesis that in every set
of $n$ horses, all are the same color.  For the base case, note that
in every set containing a single horse, all are the same color
trivially.  Now, assume that the induction hypothesis holds for every
set of $n \geq 1$ horses in order to prove that it holds for every set
of $n+1$ horses.  Consider an arbitrary set of $n+1$ horses, $h_1,
h_2, \ldots, h_{n+1}$.  By induction, $h_1, h_2, \ldots, h_{n}$ are
all the same color.  Similarly, $h_2, \ldots, h_{n+1}$ are all the
same color.  Therefore, horse $h_1$ is the same color as horses $h_2,
\ldots, h_n$, which are the same color as horse $h_{n+1}$.  It follows
that in every set of $n+1$ horses, all are the same color.
\end{proof}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}

% This proof is a precursor to the standard n^2 = O(n) proof, but does not
% require asymptotic notation.

\begin{claim}
The sum $1 + 2 + \cdots + n$ is at most some positive constant
times~$n$.
\end{claim}

\begin{proof}
The proof is by induction on $n$ with the claim as the hypothesis.  If
$n = 1$, then the sum evaluates to $1$, which is at most $c n$, where
$c$ is any constant greater than or equal to~$1$.

For the induction step, assume that the statement is true for $n$,
that is, that

\begin{eqnarray*}
1 + 2 + \cdots + n & \leq & cn
\end{eqnarray*}

\noindent for some positive constant $c$.  Adding $n+1$ to both sides,
we obtain

\begin{eqnarray*}
1 + 2 + \cdots + n + (n+1) & \leq & cn + (n+1) \\
	& \leq & (c + 1) (n + 1).
\end{eqnarray*}

\noindent Since $c$ is a positive constant, so is $c + 1$.  Therefore,
the sum is at most some positive constant times $n + 1$ as claimed.
\end{proof}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}

\end{document}
