\problemdata     
{induction-5}           
{false proofs, strong induction}              
{}              
{F94,S98-PS2,S01-PS2} 		
{S01 Karger}        	


\begin{problem}
Pinpoint, and illustrate with a counterexample, \emph{exactly}
where the following suggested proofs go awry.

\bparts
\ppart Claim 1: $(\forall \mbox{real } x) (\forall n\in \naturals) : x^n=1$.

Suggested proof by strong induction on $n$:

(Base case, $ n= 0$) $x^n = x^0=1$ by definition of ``zeroth power'' of a
real number.

(Strong Induction hypothesis) For all $k\leq n: x^k=1$.

We must show that $x^{n+1}=1.$ By the strong inductive hypothesis, with
$k=n$ and $k=1,$ we have $x^n=1$ and $x^1=1$.  So,
\[x^{n+1}=x^nx^1 = 1\times 1=1.\] \qed

\solution{
The proof of the induction step is not correct when $n=0$.  In this case,
$k=1$ is not $\leq n$, so we cannot assume by strong induction that $x^1 =
1$, which of course it is not when $x\neq 1$.
}

\ppart Claim 2: For any positive integers $p, n, x_1, x_2,\ldots,
x_n$, if $p \divides x_1x_2\ldots x_n$, then $p \divides x_i$ for some
$1\leq i\leq n$.

Suggested proof by strong induction on $n$:

(Base case, $n= 1$) When $n=1$, we have $p \divides x_1$, therefore we
can let $i=1$ and conclude $p \divides x_i$.

(Induction case) Now assuming the claim holds for all $k\leq n$, we must
prove it for $n+1$.

So suppose $p \divides x_1x_2\ldots x_{n+1}$.  Let $y_n = x_n
x_{n+1}$, so $x_1x_2\ldots x_{n+1} = x_1x_2\ldots x_{n-1}y_n$.  Since
the righthand side of this equality is a product of $n$ terms, we have
by induction that $p$ divides one of them.  If $p \divides x_i$ for
some $i < n$, then we have the desired $i$.  Otherwise $p \divides
y_n$.  But since $y_n$ is a product of the two terms $x_n, x_{n+1}$,
we have by strong induction that $p$ divides one of them.  So in this
case $p \divides x_i$ for some $i = n$ or $i = n+1$. \qed

\solution{

The statement ``we have by strong induction that $p$ divides one of them''
is the place where the proof breaks down: it appeals to strong induction
to justify applying the induction hypothesis for $2=k\leq n$.  But the
base case was $n=1$, so we can't assume $2 \leq n$.  Note that the
reasoning above is fine for every $n\geq 2$, so the whole proof would be
fine if we had an argument to prove the claim for $n+1=2$.  But of course
we can't prove it for $n+1=2$ because it isn't true: let $p=6, x_1 =2, x_2
=3$.  Even though the reasoning is fine for every $n\geq 2$, the fact that
it failed for $n=1$ let us deduce a patently false result.
}

\eparts

\end{problem}
