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

Question

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.

Answer 1

Hint: $1=1+0\neq 0+0$. Study $P(1)$.

Answer 2

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$.

Answer 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)

Answer 4

Whenever you have to check induction proofs, you should apply the general case in order to prove the first step of the induction. In this particular situation you want to prove P(1): $7*1 = 0$.

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

In the first step, this means:

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

This statement already shows where the problem is in the induction proof, because the only natural number less than 1 is 0, and 1 cannot be expressed as $0 + 0$.

Answer 5

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!