42
$\begingroup$

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.

$\endgroup$
  • 25
    $\begingroup$ Can you really always find natural numbers $i, j$ such that $0 \leq i, j \leq k$ and $i+j = k+1$? $\endgroup$ – Alex G. Oct 13 '16 at 4:01
  • 3
    $\begingroup$ No. The "proof" assumes that for any $k\geq 0$, there exist natural numbers $i, j$ such that $0\leq i, j\leq k$ and $i+j = k+1$ $\endgroup$ – Alex G. Oct 13 '16 at 4:05
  • 43
    $\begingroup$ 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)$, so the number to look at is $k+1=1$, that is, $k=0$. $\endgroup$ – celtschk Oct 13 '16 at 8:26
  • 11
    $\begingroup$ As a matter of English, you can disprove a false theorem (i.e. an untrue statement that is claimed to be a theorem) but not a false proof. The word you need is refute: a false proof (of a real or false theorem) may be refuted. A false theorem may also be refuted, by disproving it (though not by refuting a false proof of it). $\endgroup$ – John Bentin Oct 13 '16 at 12:48
  • 7
    $\begingroup$ en.wikipedia.org/wiki/All_horses_are_the_same_color $\endgroup$ – v7d8dpo4 Oct 13 '16 at 16:12
88
$\begingroup$

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

$\endgroup$
44
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ This is the best answer to the actually posed question, how to find the error in an induction proof of an obviously false statement. The only thing to add is that this method will find at least one problem with the inductive argument, but there could also be other problems that appear at larger values of n. $\endgroup$ – zyx Oct 13 '16 at 20:46
  • 1
    $\begingroup$ @zyx by the well-ordering principle there is a smallest such problematic number... $\endgroup$ – djechlin Oct 13 '16 at 20:50
  • $\begingroup$ It's an interesting question whether all errors in the induction step can be found by examining a finite set of "problematic numbers" and whether this can be done effectively (given that the conclusion is false for all $n \geq N$ for a known $N$). I am not sure if just considering larger and larger problematic numbers will catch everything. @djechlin $\endgroup$ – zyx Oct 13 '16 at 20:59
  • $\begingroup$ @zyx you're asking whether a proof can contain an infinite number of errors? I mean each step could also use the fact that $n^2 > n$ for all $n \geq 0$, Then each step would have an error in it, and there would be an infinite number of errors. One could fix the error that $n^2 > n$ is false for $n > 0$ by replacing to the less obviously fallacious claim that $n^2 > n$ only when $n \geq 1$, so that each error would also have a fix that would leave an infinite number of errors. $\endgroup$ – djechlin Oct 13 '16 at 21:05
  • $\begingroup$ @djechlin, the proof is finite, so has only a finite number of erroneous statements. I'm asking whether there is a form of the "problematic numbers" strategy that is guaranteed to uncover them all. I suspect there is not unless you have some way of computing, for every step of the proof, infinitely many $n$ where the inductive argument requires that step to be true in order for the implication $n \to n+1$ to hold. $\endgroup$ – zyx Oct 13 '16 at 21:33
15
$\begingroup$

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)

$\endgroup$
  • 8
    $\begingroup$ This is true but problematic for people learning induction for the first time. You're right that fixing the proof (if it were possible) would require a bigger base case. But the actual error (as in, problematic line in the proof) is in the step case (which has been pointed out several times). $\endgroup$ – Richard Rast Oct 13 '16 at 15:57
11
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is good advice, but not always sufficient; it's possible to write a bogus inductive "proof" where the general case only fails after two or more steps. For a simple example, consider an attempted proof that all odd numbers greater than 1 are primes, with the base case "3 is prime" and the (obviously false) induction step "$n$ is prime $\implies$ $n+2$ is prime". $\endgroup$ – Ilmari Karonen Oct 13 '16 at 19:46

protected by user223391 Oct 28 '16 at 16:59

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?