Can't find the flaw in the reasoning for this proof by induction?

Question

I was looking over this problem and I'm not sure what's wrong with this proof by induction.

Here is the question:

Find the flaw in this induction proof.

Claim $3n=0$ for all $n\ge 0$.

Base for $n=0$, $3n=3(0)=0$

Assume Induction Hypothesis: $3k =0$ for all $0\le k\le n$

Write $n+1=a+b$ where $a>0$ and $b>0$ are natural numbers each less than $n+1$

Then $3(n+1) = 3(a+b) = 3a + 3b$

Apply Induction hypothesis to $3a$ and $3b$, showing that $3a=0$ and $3b=0$. Therefore, $3(n+1)=0$

The statement they are trying to prove is clearly absurd but I'm having trouble with the logic in the proof by induction. It just seems like the person who wrote this proof used strong induction and applied the induction hypothesis to proof the implication.

Answer 1

The problem is it doesn't work for the first step after the base case: there do not exist $a \gt 0$, $b \gt 0$ such that $a + b = n + 1$ when $n = 0$. This is a variant of all horses are the same color.

Answer 2

It says "write n+1 = a +b where a and b are greater than 0". That can not be done in your base case n=0. You may not make any assumptions in your induction step that are not equally valid in the initial case.

In other words... your induction step assumes both 3k = 0 AND k $\ge $ 1. You never made (and can NOT make) any initial case where both are true.

Answer 3

Others have given you the reason that the prove breaks down. Let me explain instead how to find the fault. We know that the claim is true for $n = 0$ but false for $n = 1$. Hence something must go wrong for $n = 1$. Since the claim for $n = 1$ relies only on the claim for $n = 0$, and the latter is true, what must go wrong is the step where we show that the claim for $n = 0$ implies the claim for $n = 1$. This leads to the discovery shared by the other answers, that $1$ cannot be written as a sum of two smaller natural numbers.

Here is another way. Often we do regular induction, in which we derive $P(n+1)$ from $P(n)$. Here we use strong induction, but that seems unnecessary: if $n+1 = a+b$, can't we just take $b = 1$? That will allow deriving $P(n+1)$ from $P(n)$ and $P(1)$. Once we consider the consequences for $n = 1$, we immediately find the mistake.