Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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? .

share|improve this question
    
I'm sorry, but I'm a bit confused. If, say, $a=2$ then this doesn't hold...I mean, $a^n\neq 1$ unless, what, $a=1$ or $n=0$ for $n\in\mathbb{N}$. Unless I'm missing something? What page of Knuth is this on? –  user1729 Aug 5 '11 at 13:36
    
Page 38. Volume 1. Third ed. Ex 2 –  Dilawar Aug 5 '11 at 13:38
    
Hmm...my p38 starts at problem 36! –  user1729 Aug 5 '11 at 13:40
1  
Okay, well, which section? –  user1729 Aug 5 '11 at 13:44
1  
Ah, well, the question (on p18 of mine) is trying to get you to find the problem with the proof! It begins "There must be something wrong with the following proof. What is it?". It has nothing to do with the difference between strong and weak induction! –  user1729 Aug 5 '11 at 13:47

3 Answers 3

up vote 4 down vote accepted

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$.

share|improve this answer

Knuth isn't pointing out anything wrong with weak induction. If you write it out formally: your statement P(n) is "$a^{n-1} = 1$", and you've checked that P(1) holds, but in proving that P(n+1) holds, you've assumed both P(n) (in the numerator) and P(n-1) (in the denominator). One "base case" isn't enough here: you need two. That is, you need to show either that P(0) and P(1) hold or that P(1) and P(2) hold. But neither of these is true, so the proof fails.

share|improve this answer
    
Yes, Knuth does not make this point. Sorry for composing the sentence this way. I have edited the question. –  Dilawar Aug 5 '11 at 13:52

The proof you're presenting has an error in it (in the formula) and can't be used to demonstrate anything.

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

Back to the original question. Both the strong and weak principles can be used to proof theorems, the weak having limitation doesn't mean it's sometimes false as you're presenting, by weak it mean it depends on a larger set of predicates thus weaker in deductive power, also it means it can be derived from the strong but not necessarily vice-versa.

share|improve this answer
    
There is no error. The assumption was that the theorem is true for $1, 2, \dots, n$. In particular, it is assumed $a^{(n-1)-1} = a^{n-2} = 1$ which is how the value one is obtained. Of course, the assumption is false, that is the point of the discussion, but the manipulation is fine. –  Michael Albanese Aug 18 at 16:49
    
I see where he is coming from now. Using n-2 to induce n is wrong that it never crossed my mind. –  Gasso Aug 25 at 10:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.