Where is the error in this proof by induction?

96 Views Asked by At

My assertion is that for any positive integer $n$, the following statement holds true: $a^{n-1} = 1$. The following is a preliminary proof by induction on the positive integer $n$: If $n = 1$ then $a^{n-1} = a^0 = 1$ and So the statement is correct in this case. Now take $n > 1$ and suppose , as an induction hypothesis, that $a^{k-1} = 1$ when $k = n-1, n-2, ...,1$. We then have: $a^{n-1} = a^{n-2} a^{1} = a^{n-2} \frac{a^{n-2}}{a^{n-3}} = 1 * \frac{1}{1} = 1$. Therefore, we have established that the statement holds true for every positive integer $n$. At what point during the induction process was the mistake made?

2

There are 2 best solutions below

0
On

Notice that you have to use $a^{n-2}$ and $a^{n-3}$ in the last step, which are for $n=2,3$ not covered by proving the statement for $n=1$. This means that before using the induction hypothesis, you would have to prove the statement for all of $n=1,2,3$, which of course is not possible (since the statement is wrong).

1
On

Simple mistake

You take $k = n - 2$ Now you assume for $a^{n-2}$=1 And then you prove for whenever $a^{n-2}=1$, then
$a^{n-1}=1$

But how do you assume $a^{n-3}=1$. That is a wrong assumption. Because when n=1, you show your statement is correct. When n=2, n-2=0 but n-3=-1, so does the statement hold true? You have only the assumption that P(k) is true while proving P(k+1) is true and no other assumption.