TAOCP 1.2.1 Exercise 2

Section 1.2.1: Mathematical Induction

Exercise 2. ▶ [15] There must be something wrong with the following proof. What is it? “Theorem. Let $a$ be any positive number. For all positive integers $n$ we have $a^{n-1} = 1$. Proof. If $n = 1$, $a^{n-1} = a^{1-1} = a^0 = 1$. And by induction, assuming that the theorem is true for $1, 2, \ldots, n$, we have

$$a^{(n+1)-1} = a^n = \frac{a^{n-1} \times a^{n-1}}{a^{(n-1)-1}} = \frac{1 \times 1}{1} = 1;$$

so the theorem is true for $n + 1$ as well.”

Verified: yes
Solve time: 35s

Solution

The error occurs in the inductive step when the proof attempts to establish $P(n+1)$ from the assumptions $P(1),\ldots,P(n)$.

The argument writes

$$ a^n = \frac{a^{n-1}\times a^{n-1}}{a^{(n-1)-1}}, $$

then replaces each exponent by $1$ using the induction hypothesis. This replacement requires the statements

$$ a^{n-1}=1 \quad\text{and}\quad a^{(n-1)-1}=1 $$

to belong to the induction assumptions.

The first statement is $P(n)$, which is legitimate. The second statement is $P(n-1)$, since

$$ P(n-1):\qquad a^{(n-1)-1}=1. $$

Therefore the proof uses $P(n-1)$.

But when $n=1$, the inductive step would require $P(0)$:

$$ a^{(1-1)-1}=a^{-1}=1. $$

The induction hypothesis includes only $P(1)$, because there are no positive integers less than $1$. Hence the argument does not establish $P(2)$.

Indeed, substituting $n=1$ into the displayed calculation gives

$$ a^1 = \frac{a^0a^0}{a^{-1}}, $$

and the denominator cannot be replaced by $1$ from the induction hypothesis.

Thus the inductive step is invalid for the case $n=1$. The proof fails because it assumes a statement outside the range covered by the induction hypothesis. ∎