How do I find a flaw in this false proof that $7n = 0$ for all natural numbers?

This is my last homework problem and I've been looking at it for a while. I cannot nail down what is wrong with this proof even though its obvious it is wrong based on its conclusion. Here it is:

Find the flaw in the following bogus proof by strong induction that for all $n \in \Bbb N$, $7n = 0$.

Let $P(n)$ denote the statement that $7n = 0$.

Base case: Show $P(0)$ holds.

Since $7 \cdot 0 = 0$, $P(0)$ holds.

Inductive step: Assume $7·j = 0$ for all natural numbers $j$ where $0 \le j \le k$ (induction hypothesis). Show $P(k + 1)$: $7(k + 1) = 0$.

Write $k + 1 = i + j$, where $i$ and $j$ are natural numbers less than $k + 1$. Then, using the induction hypothesis, we get $7(k + 1) = 7(i + j) = 7i + 7j = 0 + 0 = 0$. So $P(k + 1)$ holds.

Therefore by strong induction, $P(n)$ holds for all $n \in \Bbb N$.

So the base case is true and I would be surprised if that's where the issue is.

The inductive step is likely where the flaw is. I don't see anything wrong with the strong induction declaration and hypothesis though and the math adds up! I feel like its so obvious that I'm just jumping over it in my head.

Solution 1:

The problem is here:

Write $k + 1 = i + j$, where $i$ and $j$ are natural numbers less than $k + 1$.

If $k = 0$, then you are trying to write $1 = i+j$ where $i$ and $j$ are natural numbers less than $1$. The only option for $i$ and $j$ is $0$, but $0+0 \ne 1$.

Solution 2:

As a general rule: For fake induction proofs, find the smallest case where the conclusion does not hold, and then do each step in detail with the corresponding numbers inserted, so that it should proof that exact case. That way you will almost always quickly find the problem.

In this case, the smallest failing case is $P(1)$, as that claims $7\cdot 1=0$ which is clearly wrong. Therefore the number to look at is $k+1=1$, that is, $k=0$.

So let's look at the inductive step, and insert $k=0$:

Inductive step: Assume $7\cdot j=0$ for all natural numbers $j$ where $0\le j\le 0$ (induction hypothesis). Show $P(k+1): 7(k+1)=0$.

The only number with $0\le j\le 0$ is $j=0$, so the induction hypothesis is that $7\cdot 0=0$, which clearly is true.

Write $0+1=i+j$, where $i$ and $j$ are natural numbers less than $k+1$.

The only natural number less than $1$ is $0$. Therefore we have to write $0+1 = 0+0$ … oops, that's not right! Error found!

Solution 3:

Actually, the problem is in the base case — in particular, $P(0)$ isn't enough of a base case.

The inductive step for proving $P(n)$ depends on writing $n$ as a sum of two smaller natural numbers; you can do this when $n \geq 2$, but you can't do this when $n=1$.

If you have both $P(0)$ and $P(1)$ in the base case, that's enough to make the inductive step work.

(of course, you can't prove $P(1)$, so you can't prove the base case)