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).
 A: Here is a collection of Flawed Induction Proofs.
A: 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.” 
A: 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$.

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

A: 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. 

A: 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!
A: 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.

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

A: 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.

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

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

