# Fake induction proofs

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

• 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. – Michael Hardy May 21 at 21:25

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

• 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.] – Daniel W. Farlow Mar 24 '15 at 13:43
• 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. – MCT Mar 25 '15 at 1:36
• @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. – Daniel W. Farlow Mar 25 '15 at 3:09
• @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. – MCT Mar 25 '15 at 16:23
• 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$. – Barry Cipra Mar 27 '15 at 20:16

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!

• 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.] – Daniel W. Farlow Mar 24 '15 at 14:15
• 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.) – Brian Tung Mar 24 '15 at 23:10
• @crash Unfortunately after reading through several of these "fake proof" threads, I have become distrustful of the word "divide"! – Brady Gilg Mar 26 '15 at 23:40
• @BradyGilg what do you mean exactly? That the proofs are really deceptive or you don't like the topic being considered? – Daniel W. Farlow Mar 26 '15 at 23:43
• @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. – Brady Gilg Mar 26 '15 at 23:58

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.

• 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.] – Daniel W. Farlow Mar 24 '15 at 13:43

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.

• It's in Fundamental Algorithms, at the very beginning. – Andrew Woods Mar 27 '15 at 20:11
• 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.] – Daniel W. Farlow Mar 27 '15 at 20:11
• Can you explain the flaw in more detail, this proof seems genius – Milan Jul 2 '19 at 16:41
• @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. – user1001001 Jan 12 at 17:35
• @pkwssis I got it in the meantime, its very dirty – Milan Jan 12 at 18:15

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

• 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.] – Daniel W. Farlow Mar 24 '15 at 13:43

Here is a collection of Flawed Induction Proofs.

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

• 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.] – Daniel W. Farlow Mar 24 '15 at 13:43

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

• 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.] – Daniel W. Farlow Mar 27 '15 at 18:35

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

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.

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.

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