33
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ Its saying that 3n is equal to 0 for any n>0. An easy counter example would be n=1 which makes 3(1) = 3 which is not equal to 0. $\endgroup$
    – user262291
    Commented Feb 19, 2016 at 4:47
  • $\begingroup$ Yes you are right, he used strong induction. $\endgroup$
    – SchrodingersCat
    Commented Feb 19, 2016 at 4:47
  • $\begingroup$ Sorry, misread the question at first. My fault, so I deleted the comment $\endgroup$
    – zz20s
    Commented Feb 19, 2016 at 4:48
  • 3
    $\begingroup$ So, it's not enough to make the step for some $k$. You must make it for every $k\ge 0$ $\endgroup$
    – TobiMcNamobi
    Commented Feb 19, 2016 at 12:09
  • 2
    $\begingroup$ Note that in general, the introduction of values that don't exist or expressions that are undefined is a pretty typical way to introduce subtle errors into a proof, so always be sure to check that all values can actually exist and that operations do not lead to undefined behavior. $\endgroup$
    – Kyle Strand
    Commented Feb 20, 2016 at 0:29

3 Answers 3

Reset to default
70
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What is the exact answer for the Same Colour horse argument ? $\endgroup$
    – Saikat
    Commented Feb 19, 2016 at 12:39
  • 1
    $\begingroup$ Imagine doing the induction step on the base case n = 1. Induction step: Assume true for n (n=1). Take a group of n+1 (2) horses. Remove a horse. The remaining n (1) horses are all the same color. Remove another horse. The remaining n-1 (0) horses are the same color as the horse you removed (no, they aren't; there are no remaining horse). Add the first horse. You have n (1) horses so they are all the same color as the remaining horses (no, it isn't because there were no remaining horses). Add the second horse back again. It color hasn't changed (no, but the other horse isn't the same $\endgroup$
    – fleablood
    Commented Feb 19, 2016 at 17:35
21
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ @user262291: this should be the accepted answer $\endgroup$
    – image357
    Commented Feb 19, 2016 at 12:58
  • 1
    $\begingroup$ The problem is not that "$a$ and $b$ are greater than $0$" fails for $n=0$, but that it fails for $n=1$. Since your base case requires a direct proof anyway, there's no reason it must satisfy the specific assumptions of the induction step; all that's required is that every case after the base case satisfies the necessary assumptions. $\endgroup$
    – Kyle Strand
    Commented Feb 20, 2016 at 0:26
  • 2
    $\begingroup$ It doesn't fail for n =1. (a=1,b=1 then n+1=a+b). If we need a presumption to get from k to k+1, that presumption must hold in our base case. Otherwise we can't ever get beyond the base case. $\endgroup$
    – fleablood
    Commented Feb 20, 2016 at 1:00
  • $\begingroup$ @fleablood: What Kyle Strand is getting at is that the actual "base case" or "initial case" in the OP's proof is the (correct) statement that $3 n = 0$ when $n = 0$. Your answer is using the terms "base case" and "initial case" to refer to the lowest-valued instance of the induction step (i.e., the statement that $3 n = 0 \rightarrow 3 ( n + 1 ) = 0$ when $n = 0$), which is a very confusing abuse of terminology. $\endgroup$
    – ruakh
    Commented Feb 20, 2016 at 18:48
  • 1
    $\begingroup$ That's the base case I am assuming too. And it is when n=0 that no two a,b greater than 0 so that a+b =n+1 can exist. You can not use the assumption in the induction step because you have not established that the exist in any case where 3n =0. The only case we've established where 3n=0 is n=0 and in that case no such a,b exist. I'm not abusing "base case", base case means n=0. What we rely upon in the induction case must be valid in the base case. Else our induction isn't valid. Or alternatively, for our induction to be valid we must find a base as case where both assumptions are true. $\endgroup$
    – fleablood
    Commented Feb 20, 2016 at 19:57
13
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .