84
$\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$
1
  • $\begingroup$ I don't remember the erroneous proof of the four-color theorem that was published in the 1890s, but I wonder if that might have been one of these. $\endgroup$ Commented May 21, 2020 at 21:25

11 Answers 11

85
$\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$
5
  • 56
    $\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$ Commented Mar 24, 2015 at 13:43
  • 4
    $\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$
    – MT_
    Commented Mar 25, 2015 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$ Commented Mar 25, 2015 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$
    – MT_
    Commented Mar 25, 2015 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$ Commented Mar 27, 2015 at 20:16
50
+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$
8
  • 16
    $\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$ Commented Mar 24, 2015 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
    Commented Mar 24, 2015 at 23:10
  • 2
    $\begingroup$ @crash Unfortunately after reading through several of these "fake proof" threads, I have become distrustful of the word "divide"! $\endgroup$
    – Brady Gilg
    Commented Mar 26, 2015 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$ Commented Mar 26, 2015 at 23:43
  • 1
    $\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
    Commented Mar 26, 2015 at 23:58
45
$\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$
1
  • 18
    $\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$ Commented Mar 24, 2015 at 13:43
25
$\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$
5
  • 1
    $\begingroup$ It's in Fundamental Algorithms, at the very beginning. $\endgroup$ Commented Mar 27, 2015 at 20:11
  • 17
    $\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$ Commented Mar 27, 2015 at 20:11
  • 1
    $\begingroup$ Can you explain the flaw in more detail, this proof seems genius $\endgroup$
    – Milan
    Commented Jul 2, 2019 at 16:41
  • 4
    $\begingroup$ @Milan $\left(\dfrac{1}{1\cdot 2} + \cdots + \dfrac{1}{(n-1)\cdot n}\right)$ has $n-1$ terms, so according to the inductive hypothesis $\dfrac{3}{2}-\dfrac{1}{n-1}$ should be substituted in place of that sum. $\endgroup$ Commented Jan 12, 2020 at 17:35
  • 1
    $\begingroup$ @pkwssis I got it in the meantime, its very dirty $\endgroup$
    – Milan
    Commented Jan 12, 2020 at 18:15
15
$\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$
1
  • 8
    $\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$ Commented Mar 24, 2015 at 13:43
10
$\begingroup$

Here is a collection of Flawed Induction Proofs.

$\endgroup$
8
$\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$
7
$\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$
1
  • 3
    $\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$ Commented Mar 24, 2015 at 13:43
7
$\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
  • 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$ Commented Mar 27, 2015 at 18:35
4
$\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$
2
$\begingroup$

Claim:

If $a$ is an odd square modulo $m$, then $a$ is a square modulo $2m$.

Proof:

Let $m=2^v k$ where $k$ is $m$'s largest odd factor. Proceed by induction on $v$.

Base case:

$v=0$, so $m=k$ is odd.

$a$ is a square modulo $k$, so, for some $x$, $k\mid x^2-a$. Modulo $2k$, \begin{align*} (k+x)^2 &= k^2+2kx+x^2\\ &= k+x^2\tag{$k^2=k$ as $k$ is odd; $2kx=0$} \end{align*} so $x^2$ and $(k+x)^2$ are $a$ and $k+a$ in some order. So $a$ is a square modulo $2k$.

Inductive step:

$a$ is a square modulo $2^v k$ so there is an $x$ where $x^2=a\mod 2^v k$. As the base case is proved, we may suppose that $m$ is even and $v\geqslant1$. This means that, as $a$ is odd, $x$ is odd. Knowing that $m$ is even also enables us to refine $x$: Modulo $m$, \begin{align*} (m/2+x)^2 &= (2^{v-1} k+x)^2\\ &= 2^{2v-2} k^2+2\cdot2^{v-1} kx+x^2\\ &=2^{v} kx+x^2\\ &=x^2\\ &=a \end{align*} as the other terms are multiples of $m=2^v k$. That is, we may take $0<x<m/2$.

Modulo $2m$, \begin{align*} (m/2+x)^2 &= (2^{v-1} k+x)^2\\ &= 2^{2v-2}k^2+2\cdot2^{v-1} kx+x^2\\ &=2^v kx+x^2\\ &=mx+x^2\\ &=m+x^2\tag{as $x$ is odd} \end{align*} Thus $x^2$ and $(m/2+x)^2$ are $a$ and $m+a$ in some order. Thus $a$ is a square modulo $2m$. QED.

Flaw:

The base case is valid. The inductive step relies on $2^{v+1}k\mid2^{2v-2}k^2$, which is true only if $2v-2\geqslant v+1$ i.e. $v\geqslant3$ i.e. $8\mid m$.

$\endgroup$

You must log in to answer this question.

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