In Mathematics literature, I am under the impression that there are at least two (non-trivially different) definition of Mathematical induction. I am assuming one is a weak form and the other is strong.
Def 1 (weak form) (I believe that I have read it many times) Prove that $P$ holds for base case e.g. $P$ holds for 1; assume that $P$ holds for $n$ and prove that $P$ holds for $n+1$ then $P$ holds for all $n$.
Def 2 (strong form) Prove that $P$ holds for base case, give a proof that "If all of $P(1), P(2), …, P(n)$ are true, then $P(n+1)$ is also true"; this proof is valid for any positive integer $n$.
A problem is posed by Knuth in his book (vol 1). When I worked it out, it points out the limitation of def 1 quite nicely. (Section 2 : Mathematical Induction, p38, Ex 3. Third Edition.)
Theorem Let $a$ be any positive number. For all positive number $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 if 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 \times 1}{1} = 1$
so the theorem is true for $n+1$ as well.
This proof is wrong as far as the def 2 is concerned since we have not shown that it is true of case $n=2$.
Their are many cases where Def 1 is sufficient to prove the theorem. Under what conditions we can use Def 1 ? Is my categorisation of weak and strong form is correct? Is def 1 not at all sufficient?
EDIT : Just found out a related discussion on this What is the second principle of finite induction? .
Best Answer
The two forms of induction are equally valid. The second is called complete or strong induction and can be derived from the first.
The problem in the "proof" has nothing to do with this distinction. The proof is equally invalid under either scheme, since it uses the case $n=0$ to prove the case $n=2$, but the claim does not hold for $n=0$.