Flawed proof by induction that $a^{n-1}=1$

Question

Donald Knuth "The Art of Computer Programming" Section 1.2.1 has an exercise No.2, the solution to which I don't understand. Exercise:

There must be something wrong with this 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, ..., n$, we have $a^{(n+1)-1}=a^n=\frac{a^{n-1}\times a^{n-1}}{a^{(n-1)-1}}=\frac{1\times1}{1}=1$; so the theorem is true for $n+1$ as well.

As far as I understand the proof by induction, the solution should be approximately following:
$a^{1-1}=1$
Assume that $a^{n-1}=1$;
Therefore $a^{(n+1)-1}=1\times a$;
So $a^{(n+1)-1}$ does not equal $a^{n-1}$ and does not equal $1$, unless $a=1$

The solution to exercise reads:

The theorem has not been proved for $n=2$; in the second part of the proof, take $n=1$; we assume there that $a^{-1}=1$. If this condition is true (so that $a=1$), the theorem is indeed valid.

I want to compare it to another, correct, proof by induction in the example from here:

Adding up Odd Numbers $1+3+5+...+(2n−1)=n^2$

1. Show it is true for $n=1$
   $1=1^2$ is True
2. Assume it is true for $n=k$
   $1+3+5+...+(2k−1) = k^2$ is True (An assumption!)
3. Now, prove it is true for $(k+1)$
   $1 + 3 + 5 + ... + (2k−1) + (2(k+1)−1) = (k+1)^2$
   We know that $1 + 3 + 5 + ... + (2k−1) = k^2$ (the assumption above),
   so we can do a replacement for all but the last term:
   $k^2 + (2(k+1)−1) = (k+1)^2$
   Now expand all terms:
   $k^2 + 2k + 2 − 1 = k^2 + 2k+1$
   And simplify:
   $k^2 + 2k + 1 = k^2 + 2k + 1$
   They are the same! So it is true.
   So: $1 + 3 + 5 + ... + (2(k+1)−1) = (k+1)^2$ is True

Returning to the first example, I didn't quite understand the meaning of the phrase

The theorem has not been proved for $n=2$;

In the second (correct) proof there is no proving that it holds for $n=2$, despite covering the same topic. And Knuth himself has the proof of the theorem $1+3+5+...+(2k−1) = k^2$ similar to the one above, where he too doesn't prove it for $k=2$. So what did he mean by this phrase? Does he mean that there already is an exception in the rule stated when we take arbitrary $n$, for example $n=2$, so therefore it wouldn't hold for all examples anyway? But taking arbitrary numbers and putting it into equation instead of $n$ doesn't seems to be an effective and systematic way to debunk such proofs. How would you explain what is wrong with the exercise?

Answer 1

To understand what's happening in the first example, it suffices to substitute actual values for $n$. We clearly have no argument with $a^0 = 1$, which corresponds to the case $n = 1$. But when $n = 2$, the inductive reasoning step looks like this:

$$a^{2-1} = \frac{a^{1-1} a^{1-1}}{a^{0-1}} = \frac{a^0 a^0}{a^{-1}}.$$ So the next step fails immediately because the base case begins at $n = 1$, not $n = 0$; that is to say, $a^{-1} \ne 1$ as required for the inductive step to remain true.

The reason why the second example does not suffer from this defect is because the inductive step does not rely on an incorrect assumption about an earlier case being true. You don't have this problem in your example because all of the algebraic steps are valid and supported by the induction hypothesis. In the first example, this is not so, because the very next case is assuming that $a^{-1} = 1$.

Indeed, if $a = 1$, thereby satisfying this assumption, then it is true that $a^{n-1} = 1$ for all $n$. The way in which the inductive step fails actually illustrates precisely when the theorem is true.

Answer 2

The crux of complete induction is that we are trying to show that given the statement is true for $\{1,\ldots n\}$, it must be true for $n+1$. For the question at hand, this means that we are allowed to assume that $a^{k-1}=1$ if $k \in \{1,\ldots n\}$. Hence, we are allowed to assume that $a^0=1,\ldots,a^{n-1}=1$.

For $n=2$, this means that we are only allowed to assume that the statement is true for $n=1$ (i.e. $a^0=1)$. Now, we want to show that the statement is true for $n+1=2$; that is, we want to show $a^{1}=1$. Already alarm bells should be ringing in your mind! The inductive step is $$ a^{(n+1)-1}=a^n=\frac{a^{n-1}\cdot a^{n-1}}{a^{n-2}} = \frac{1 \cdot 1}{1}=1\, . $$ Substituting $n+1=2$ into the above equation, it reads $$ a^{2-1}=a^1=\frac{a^{0}\cdot a^{0}}{a^{1-2}}=\frac{1}{a^{-1}}\color{red}{=}1 \, . $$ The last equality does not hold: $$ \frac{1}{a^{-1}}=a \neq 1 \, . $$ Induction fails because we are relying on the fact that the statement being true for $n-2$. When $n=1$, this amounts to assuming that $a^{-1}=1$, which is clearly not true for all $a$. We are only allowed to assume that the statement is true for $\{1,\ldots,n\}$, and $n-2$ might not be a member of the previous set, as we have just seen. The falseness of the proof boils down to the fact that we are assuming more than we should. For induction proofs that require us to know that a statement is true for $\{1,\ldots,n\} \wedge \{n-2\}$, we need two base cases. Once we have established that the statement is true for $1$, and $2$, then things are the same as before, since $n-2 \in \{1,\ldots,n\}$.

The later examples you give are much simpler cases of induction. The type of induction used previous is called 'complete induction', where you assume that a statement is true for $\{1,\ldots,n\}$ and show it for $n+1$. To show that the sum of the first $n$ odd numbers is $n^2$, we only need to assume that it is true for $n$, and $n+1$. There is less room for error with this weaker of form of induction. Once we have established that the statement is true for $1$, it must be true for $2$, $3$, $4$, etc.

Finally, the word 'assumption' is, in my view, somewhat confusing in the context of proof by induction. Really, we are just trying to establish two things:

• The statement is true for $1$.
• If the statement is true for $n$, then it must be true for $n+1$. (Or, in the case of complete induction, if the statement is true for $\{1,\ldots,n\}$, then it must be true for $n+1$.)

Then, it follows that the statement must be true for $2$, $3$, $4$, etc. Of course, in order to show that $A$ implies $B$, we have to assume that $A$ is true in the first place. But that's kind of obvious, right? I don't know why people make a meal out of the word 'assumption'. Essentially, we are trying to show that given a statement is true for $n$, then it must be true for $n+1$. And, since it is true for $1$, it must be true for $2$, $3$, $4$, etc. That's how I like to think about induction; it's clearer that way in my mind.