\problemdata       % Takes 5 *mandatory* arguments
{backward-logic}             % latex-friendly label for the prob.
{false proof}  % The topic(s) of the problem content.
{Nick Harvey}               % Source (if known)
{never used} % Usage (list ones you are aware of).
{}        % Last revision info (author, date).


\begin{problem}

Find the errors in the following false proof.

\newtheorem*{falsetheorem}{False Theorem}

\begin{falsetheorem}
For every integer $n \geq 0$,
$$ n \cdot (-1)^n \cdot \prod_{i=-n}^{n} i = n \cdot n! \cdot n! $$
\end{falsetheorem}

\begin{proof}
We prove the theorem by induction.
Let $P(n)$ be the predicate that:
$$ n \cdot (-1)^n \cdot \prod_{i=-n}^{n} i = n \cdot n! \cdot n! $$

\noindent \textit{Base case:} We prove $P(0)$ is true.
Both sides of the equation have a factor of $n$, which is $0$,
so both sides are equal to $0$. Thus $P(0)$ is true.

\noindent \textit{Inductive step:} We want to show that $P(n)$ implies $P(n+1)$.
The proposition $P(n+1)$ is:
$$ (n+1) \cdot (-1)^{n+1} \cdot \prod_{i=-(n+1)}^{n+1} i = (n+1) \cdot (n+1)! \cdot (n+1)! $$
We extract the first and last term from the product and extract a factor of $-1$ to obtain:
$$ (n+1) \cdot (-1)^{n} \cdot (-1) \cdot (-(n+1)) \cdot (n+1) \cdot \prod_{i=-n}^{n} i
 = (n+1) \cdot (n+1)! \cdot (n+1)! $$
Next, we multiply the $(-1)$ into the $(-(n+1))$ and we use the fact that
$(n+1)! = (n+1) \cdot n!$ to obtain:
$$ (n+1) \cdot (-1)^{n} \cdot (n+1) \cdot (n+1) \cdot \prod_{i=-n}^{n} i
 = (n+1) \cdot (n+1) \cdot n! \cdot (n+1) \cdot n! $$
Next, we cancel a factor of $(n+1)^2$ from both sides to obtain:
$$ (n+1) \cdot (-1)^{n} \cdot \prod_{i=-n}^{n} i = (n+1) \cdot n! \cdot n! $$
Finally, we multiply by $\frac{n}{n+1}$ and obtain:
$$ n \cdot (-1)^{n} \cdot \prod_{i=-n}^{n} i = n \cdot n! \cdot n! $$
But this equation is true, since $P(n)$ is true by the inductive hypothesis.
Thus we have shown that $P(n+1)$ is true.

Therefore, the proposition $P(n)$ is true for all $n \geq 0$ by the principle of
induction, which proves the theorem.
\end{proof}


\end{problem}

\solution{
The theorem is false because the product on the left-hand side contains a factor of $0$.
The proof is false because it uses backward logic: we assumed that $P(n+1)$ and manipulated the
expression until we obtained something that was true.
All of the manipulations performed in the proof are equivalences except one:
when we multiply by $n/(n+1)$.
So when we try to prove that $P(0) \implies P(1)$, this step is in fact multiplying by $0$.
}

