# Find the fundamental error in the proof

The proof provided has a "fundamental error" in it, but I can't figure out what the error is.

Statement: For all non-negative integers $n$, $n$ is even.

Proof: Let $P(n)$ be the open sentence: $n$ is even.

Base Case: We show that $P(0)$ is true. Since $0=2(0)$, then 0 is even and the statement is true for $n=0$

Inductive Hypothesis: We assume the $P(i)$ is true for $0\leq i\leq k$. That is, $i$ is even for all $i$ in the range $0 \leq i \leq k$ for some $k \in \mathbb Z$ for $k \geq 0$.

Inductive Conclusion: We show that $P(k+1)$ is true. Conside $k+1$. Since $k+1 = k-1+2$ and since $0 \leq k-1 \leq k$, the by the inductive hypothesis, $k-1$ is even and 2 is even. The sum of two even numbers is even, and thus $k+1$ is even as required.

Obviously this is not true, and I have an idea as to the error, but I'm not 100% sure. I think it has something to do with the fact that they are using the strong induction method in the hypothesis, but have only provided 1 base case. Other than that, I can't see anything wrong with the actual proof method (but the proof is obviously wrong).

• The error here is that you are assuming that $P(i)$ is true for all $0 \leq i \leq k$, and by the inductive step $k+1$ you are using that it is true not 'only' for $k$, which is the previous one, but for $k-1$, which is $2$ steps below. Hence, if you actually wanted to prove that this is true for all $k$, you should include in your base case $k=1$, which is obviously not true. – Klaramun Oct 11 '17 at 7:03
• To show $P(1)=P(0+1)$ we write $1=-1+2.$ But we have not shown that $-1$ is even. Indeed, it isn't. Here is where the proof fails. – mfl Oct 11 '17 at 7:03
• The Induction Step proof is wrong: we have that $P(0)$ holds but clearly $P(1)$ does not. Thus, it is not true that $P(k) \to P(k+1)$ holds for every $k$. – Mauro ALLEGRANZA Oct 11 '17 at 7:03
• For $k=0$ the "calculation" based on $k-1$ will fail, because $k-1=-1$. – Mauro ALLEGRANZA Oct 11 '17 at 7:05

Let us rewrite the inductive step instantiated for $k=0$:
Inductive Conclusion: We show that $P(1)$ is true. Conside $1$. Since $1 = -1+2$ and since $0 \leq -1 \leq 0$, the by the inductive hypothesis, $-1$ is even and 2 is even. The sum of two even numbers is even, and thus $1$ is even as required.
• What do you mean by $0\le -1\le 0?$ – mfl Oct 11 '17 at 11:08