        \problemdata       % Takes 5 *mandatory* arguments
        {false-ind}             % latex-friendly label for the prob.
        {induction, false proofs}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F01 PS2-3} % Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

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

\begin{problemparts}
\problempart Claim 1: $\forall x \in \reals \forall n\in \naturals\; x^n=1$.

\begin{falseproof}
Proof by strong induction on $n$:

\textbf{Base case} $n= 0$: $x^n = x^0=1$ by definition of ``zeroth power'' of a
real number.

\textbf{Induction step}: By hypothesis, $x^k=1$ for all $k\leq n$.  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.
\]
\end{falseproof}

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

\problempart An integer, $m$, \emph{divides} an integer, $n$, in symbols, $m
\divides n$, iff there is an integer $k$ such that $km=n$.

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

\begin{falseproof}
Proof by strong induction on $n$.

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

\textbf{Induction step}: 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 $i = n$ or $i = n+1$.
\end{falseproof}

\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 completely false
result.}

\end{problemparts}
\end{problem}