TAOCP 1.2.1 Exercise 3
The mistake occurs in the basis step of the induction.
Section 1.2.1: Mathematical Induction
Exercise 3. [18] The following proof by induction seems correct, but for some reason the equation for $n = 6$ gives $\frac{1}{2} + \frac{1}{6} + \frac{1}{12} + \frac{1}{20} + \frac{1}{30} = \frac{5}{6}$ on the left-hand side, and $\frac{3}{2} - \frac{1}{6} = \frac{4}{3}$ on the right-hand side. Can you find a mistake? “Theorem.
$$\frac{1}{1 \times 2} + \frac{1}{2 \times 3} + \cdots + \frac{1}{(n - 1) \times n} = \frac{3}{2} - \frac{1}{n}.$$
Proof. We use induction on $n$. For $n = 1$, clearly $3/2 - 1/n = 1/(1 \times 2)$; and, assuming that the theorem is true for $n$,
$$ \begin{aligned} \frac{1}{1 \times 2} + \cdots + \frac{1}{(n - 1) \times n} + \frac{1}{n \times (n + 1)} \ = \frac{3}{2} - \frac{1}{n} + \frac{1}{n(n + 1)} &= \frac{3}{2} - \frac{1}{n} + \left( \frac{1}{n} - \frac{1}{n + 1} \right) = \frac{3}{2} - \frac{1}{n + 1} \text{.”} \end{aligned} $$
Verified: yes
Solve time: 37s
Solution
The mistake occurs in the basis step of the induction.
The theorem being proved is
$$ \frac{1}{1 \times 2}+\frac{1}{2 \times 3}+\cdots+\frac{1}{(n-1)\times n} = \frac32-\frac1n. $$
For $n=1$, the left-hand side contains no terms at all, since the first term would be
$$ \frac{1}{1\times2}, $$
but the last term is
$$ \frac{1}{(1-1)\times1}, $$
so the summation is empty. An empty sum equals $0$.
Hence for $n=1$ the equation becomes
$$ 0=\frac32-1=\frac12, $$
which is false.
The proof incorrectly asserts that when $n=1$,
$$ \frac32-\frac1n=\frac1{1\times2}. $$
Indeed,
$$ \frac32-\frac11=\frac12, \qquad \frac1{1\times2}=\frac12, $$
but this compares the right-hand side with a term that does not actually occur in the left-hand side when $n=1$.
The induction step is correct. Using
$$ \frac1{n(n+1)} = \frac1n-\frac1{n+1}, $$
one obtains
$$ \frac32-\frac1n+\frac1{n(n+1)} = \frac32-\frac1{n+1}. $$
Thus the only error is the incorrect initial case.
To make the proof valid, the theorem should be stated for $n\ge2$. Then the basis step is
$$ \frac1{1\times2} = \frac12 = \frac32-\frac12, $$
which is true, and the induction step proves the result for all $n\ge2$.
Therefore the flaw is that the induction starts with $n=1$, where the stated formula is false. ∎