65
$\begingroup$

Question: Can you provide an example of a claim where the base case holds but there is a subtle flaw in the inductive step that leads to a fake proof of a clearly erroneous result? [Note: Please do not answer with the very common all horses are the same color example.]

Comment: Sometimes inductive arguments can lead to controversial conclusions, such as the surprise exam paradox, Richard's paradox and a host of other paradoxes. However, I am interested in examples of a more mathematical nature (as opposed to linguistic) where the inductive argument is subtly flawed and leads to erroneous conclusions.

Note: If you provide an answer, please do so in a way similar to how current answers are displayed (gray out the flaw so people can be challenged to discover it).

$\endgroup$

10 Answers 10

68
$\begingroup$

Claim: $\frac{d}{dx}x^n=0$ for all $n\ge0$.

Base case: ($n=0$): $\frac{d}{dx}x^0=\frac{d}{dx}1=0$

Inductive step: Assume that $\frac{d}{dx}x^k=0$ for all $k\le n$. Then by the product rule,

$$\frac{d}{dx}x^{n+1}=\frac{d}{dx}(x^n\cdot x^1)=x^n\frac{d}{dx}x^1+\left(\frac{d}{dx}x^n\right)x^1=x^n\cdot0+0\cdot x^1=0.$$

Flaw:

In order for this to be a valid proof, the inductive step must be valid for all $n\ge0$. However, when $n=0$, one can’t use the inductive hypothesis to rewrite $\frac{d}{dx}x^1$ as $0$.

This “spoof” appears in Martin V. Day’s “An Introduction to Proofs and the Mathematical Vernacular.” Day gives its source as Edward J. Barbeau’s “Mathematical Fallacies, Flaws and Flimflam.”

$\endgroup$
  • 44
    $\begingroup$ Consider upvoting this comment if this fake proof stumped you for a moment. [Just a simple test to gauge how deceptive this argument really is.] $\endgroup$ – Daniel W. Farlow Mar 24 '15 at 13:43
  • 2
    $\begingroup$ I thought that when OP said "with a correct base step" that meant that the correct number for the base step is true as well - in this case, the base step is incorrectly used since we should start instead from $n=1$. In fact, many of the proofs in this thread have a flaw that is exactly that. $\endgroup$ – MCT Mar 25 '15 at 1:36
  • $\begingroup$ @Soke Interesting observation. I thought it was pretty clear from the example answers what is desired, but feel free to add a comment in the question body to address what you just commented on. $\endgroup$ – Daniel W. Farlow Mar 25 '15 at 3:09
  • $\begingroup$ @crash It is pretty clear what you meant. I suppose I was just hoping that there would be something that wasn't just the wrong number in the base case. $\endgroup$ – MCT Mar 25 '15 at 16:23
  • $\begingroup$ I would reformulate this as a proof by strong induction, i.e., assume it's true for all $k\lt n$ and then show ${d\over dx}x^n={d\over dx}(x^k\cdot x^{n-k})=\ldots$. $\endgroup$ – Barry Cipra Mar 27 '15 at 20:16
41
+100
$\begingroup$

Here is a "proof" of a famous identity by Ramanujan: $$\sqrt{1+\sqrt{1+2\sqrt{1+3{\sqrt{1+4\sqrt{\dots}}}}}}=2.$$

Claim: Let us prove this more general result for all $n\geq 0$: $$\sqrt{1+n\sqrt{1+(n+1)\sqrt{1+(n+2)\sqrt{1+(n+3)\sqrt{\ldots}}}}}=n+1.$$

Base case: When $n=0$, we have $\sqrt{1+0\sqrt{\dots}}=0+1$, and this is true.

Inductive step: Assume that the identity holds for some $n$ and let us prove it holds for $n+1$. By squaring both sides we get $$1+n\sqrt{1+(n+1)\sqrt{1+(n+2)\sqrt{1+(n+3)\sqrt{\ldots}}}}=n^2+2n+1.$$ Subtracting $1$ and dividing by $n$, we get $$\sqrt{1+(n+1)\sqrt{1+(n+2)\sqrt{1+(n+3)\sqrt{\ldots}}}}=n+2,$$ which is what we wanted to show. $\blacksquare$

Flaw:

We cannot divide by $n$ because at the very beginning of induction $n=0$. Moreover, one should justify the existence of the infinite nested radical.

Comment: This "proof" is funny because, in fact, it gives a correct result!

$\endgroup$
  • 15
    $\begingroup$ Consider upvoting this comment if this fake proof stumped you for a moment. [Just a simple test to gauge how deceptive this argument really is.] $\endgroup$ – Daniel W. Farlow Mar 24 '15 at 14:15
  • 2
    $\begingroup$ Can this argument be made more rigorous by considering the limit of the two sides as $n$ approaches $0$? (Just for the first induction step. After that, the induction step works as stated.) $\endgroup$ – Brian Tung Mar 24 '15 at 23:10
  • 1
    $\begingroup$ @crash Unfortunately after reading through several of these "fake proof" threads, I have become distrustful of the word "divide"! $\endgroup$ – Brady Gilg Mar 26 '15 at 23:40
  • $\begingroup$ @BradyGilg what do you mean exactly? That the proofs are really deceptive or you don't like the topic being considered? $\endgroup$ – Daniel W. Farlow Mar 26 '15 at 23:43
  • $\begingroup$ @crash That I was not fooled by the fake proof because I've been trained through experience to recognize the word "divide" as a red flag. $\endgroup$ – Brady Gilg Mar 26 '15 at 23:58
35
$\begingroup$

Claim: $a^n=1$ for all nonnegative integers $n$, whenever $a$ is a nonzero real number.

Base case: $a^0=1$ is true by the definition of $a^0$.

Inductive step: Assume that $a^m=1$ for all nonnegative integers $m$ with $m\leq k$. Then notice that $$ a^{k+1}=\frac{a^k\cdot a^k}{a^{k-1}}=\frac{1\cdot 1}{1}=1. $$

Flaw:

The flaw occurs in the inductive step where we implicitly assume that $k\geq 1$ in order for us to talk about $a^{k-1}$ in the denominator; otherwise, the exponent is not a nonnegative integer, meaning we cannot apply the inductive hypothesis. We checked the base case only for $n=0$; thus, we are not justified in assuming that $k\geq 1$ when we try to prove the statement for $k+1$ in the inductive step. It is exactly at $n=1$ that the proposition breaks down.

$\endgroup$
  • 13
    $\begingroup$ Consider upvoting this comment if this fake proof stumped you for a moment. [Just a simple test to gauge how deceptive this argument really is.] $\endgroup$ – Daniel W. Farlow Mar 24 '15 at 13:43
20
$\begingroup$

Here is one published by Knuth.

Claim: $$\underbrace{\frac1{1\cdot2}+\frac1{2\cdot3}+\ldots}_{n\text{ terms}}=\frac32-\frac1n$$

Base case: For $n=1$, we have $\frac32-\frac11=\frac1{1\cdot2}$

Inductive step: $$\left(\frac1{1\cdot2}+\ldots+\frac1{(n-1)\cdot n}\right)+\frac1{n\cdot(n+1)}=\frac32-\frac1n+\frac1{n\cdot(n+1)}$$ $$=\frac32-\frac1n+\frac1n-\frac1{n+1}=\frac32-\frac1{n+1}$$

Flaw:

The indexing is wrong. I altered the statement slightly to make it harder to spot.

$\endgroup$
  • $\begingroup$ It's in Fundamental Algorithms, at the very beginning. $\endgroup$ – Andrew Woods Mar 27 '15 at 20:11
  • 15
    $\begingroup$ Consider upvoting this comment if this fake proof stumped you for a moment. [Just a simple test to gauge how deceptive this argument really is.] $\endgroup$ – Daniel W. Farlow Mar 27 '15 at 20:11
  • $\begingroup$ Can you explain the flaw in more detail, this proof seems genius $\endgroup$ – Milan Jul 2 at 16:41
13
$\begingroup$

Claim: For every $n\in\mathbb{Z^+}$, if $x,y\in\mathbb{Z^+}$ with $\max(x,y)=n$, then $x=y$.

Base case: Suppose that $n=1$. If $\max(x,y)=1$ and $x,y\in\mathbb{Z^+}$, then $x=1$ and $y=1$.

Inductive step: Let $k\in\mathbb{Z^+}$. Assume that whenever $\max(x,y)=k$ and $x,y\in\mathbb{Z^+}$, then $x=y$. Now let $\max(x,y)=k+1$, where $x,y\in\mathbb{Z^+}$. Then $\max(x-1,y-1)=k$. By the inductive hypothesis, $x-1=y-1$. It follows that $x=y$, completing the inductive step.

Flaw:

The flaw occurs when applying the inductive hypothesis to look at $\max(x-1,y-1)$. Even though $x$ and $y$ are positive integers, $x-1$ and $y-1$ do not necessarily need to be (for example, one or even both could be $0$). This is actually what happens if we let $x=1$ and $y=2$ when $k=1$.

$\endgroup$
  • 7
    $\begingroup$ Consider upvoting this comment if this fake proof stumped you for a moment. [Just a simple test to gauge how deceptive this argument really is.] $\endgroup$ – Daniel W. Farlow Mar 24 '15 at 13:43
8
$\begingroup$

Here is a collection of Flawed Induction Proofs.

$\endgroup$
5
$\begingroup$

For each non-negative integer $n$, let $S(n)$ be the statement $S(n) : n=0.$

Claim: Every non-negative integer is equal to $0$.

Base case: $S(0)$ is clearly true.

Inductive step: Fix some $k\geq 0$ and assume that $S(0),\ldots, S(k)$ are true. To prove that $S(k+1)$ is true, observe that $S(k)$ says $k=0$ and $S(1)$ says $1=0$; hence, we have that $k+1=0+0=0$, proving $S(k+1)$. This concludes the inductive step, and hence the proof by strong induction.

Flaw:

The statement $S(1)$ does not follow from $S(0)$.

$\endgroup$
  • 1
    $\begingroup$ Consider upvoting this comment if this fake proof stumped you for a moment. [Just a simple test to gauge how deceptive this argument really is.] $\endgroup$ – Daniel W. Farlow Mar 27 '15 at 18:35
4
$\begingroup$

Claim: For every non-negative integer $n, 5n=0$.

Base case: $5\cdot 0=0$.

Inductive step: Suppose that $5j=0$ for all non-negative integers $j$ with $0\leq j\leq k$. Write $k+1=i+j$, where $i$ and $j$ are natural numbers less than $k+1$ (I am considering the natural numbers to include $0$). By the induction hypothesis, $5(k+1)=5(i+j)=5i+5j=0+0=0$.

Flaw:

The flaw occurs when going from the base case $n=0$ to the next case, $n=1$. The number $1$ cannot be written as the sum of two smaller natural numbers; thus, we cannot invoke the inductive hypothesis. In the proof, when $k=0$, we cannot write $0+1=i+j$ where $0\leq i\leq 0$ and $0\leq j\leq 0$.

$\endgroup$
  • 2
    $\begingroup$ Consider upvoting this comment if this fake proof stumped you for a moment. [Just a simple test to gauge how deceptive this argument really is.] $\endgroup$ – Daniel W. Farlow Mar 24 '15 at 13:43
3
$\begingroup$

Here's a double induction 'proof'.

Claim: For all integers $n\ge 1$ and $m\ge 0$, $n\mid m$ ($n$ divides $m$).

Proof:

Outer induction (on $n$):

Base case: Clearly $1\mid m$ for all $m\ge 0$.

Inductive step: Assuming the claim is true for $n=k$, we must show it is true for $n=k+1$. We do this by strong induction on $m$.

$\hspace{.5in}$ Inner induction (on $m$)

$\hspace{.5in}$ Base case: When $m=0$, we need $k+1 \mid 0$, which is clearly true.

$\hspace{.5in}$ Inductive step:

$\hspace{.5in}$ Assume that $k+1\mid m$ for $m=0, 1, \dots j$. From this strong induction assumption, we have $k+1\mid 1$ and $k+1 \mid j$. Hence $k+1$ divides the sum: $k+1\mid j+1$. So the result holds for $m=j+1$.

By (double) induction, we have $n\mid m$ for all integers $n\ge 1$, $m\ge 0$, as claimed.

Flaw:

On the inner induction you can't go from $m=0$ to $m=1$.

$\endgroup$
3
$\begingroup$

Claim: Given a set of $n$ points. Then these points lay on one line.

Proof:

Inductive Basis: Clearly, one point lays on one line.

Inductive Hypothesis: Given a set of $k$ points. Then these points lay on one line.

Inductive Step: Consider a set of $k+1$ points. Consider a subset of $k$ points. Then these lay on a line. Consider another subset of $k$ points. Then these lay on a line. The intersection of these sets contain $k-1$ points, so these lines are clearly the same.

Flaw:

If $k=2$, then the intersection is just a point where multiple lines go through.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.