Weak Induction vs Strong Induction
By Chi K. Ho on Monday, May 06, 2002 - 11:07 pm:

Hi !!

Could anyone please explain what the difference is between a proof by induction and a proof by strong induction ?

Are there any examples which can demonstrate that it can be proved by one but not the other ?

Thanks,
Chi

By Dan Goodman on Monday, May 06, 2002 - 11:36 pm:
If memory serves me correctly, in a proof by induction you have to prove two things, that the statement is true for n=0 (or n=1) and that the truth of the statement for n implies the truth of the statement for n+1. In stronginduction, all you need to prove is that the truth of the statement for 0≤i<n implies the truth of the statement for n. I think there is no logical distinction between the two (in other words, if you can prove it with strong induction you can prove it with induction and vice versa). In practice, in a proof by strong induction you usually need to treat the case n=0 separately anyway, but you can also assume the truth of the statements from 1 to n-1 as well as 0 and n in proving it for n+1.
By Mark Rowland on Tuesday, May 07, 2002 - 06:37 am:

what about the proof that every positive integer greater than 1 has a prime divisor ? I think this can be proved by strong induction but not ordinary (weak ?) induction

By David Loeffler on Tuesday, May 07, 2002 - 07:08 am:
You can prove the principle of strong induction from the principle ofweak induction: suppose we want to prove that some property P(n) holds for all positive integers n. Let Q(n) be the property that P(m) holds for all m≤n. Note that P(1) if and only if Q(1). If Q(n)⇒Q(n+1), then by (weak) induction Q(n) holds for all n, so P(n) holds for all n. But "Q(n)⇒Q(n+1)'' is equivalent to "P(m) for all m≤n⇒P(n+1)''. So we have proved strong induction using weak induction.

David

By Mark Rowland on Tuesday, May 07, 2002 - 09:12 pm:

indeed - weak induction implies strong induction. Which strikes me as rather perverse !!

By Chi K. Ho on Wednesday, May 08, 2002 - 12:02 am:

Haha, I agree completely !! Shouldn't the names be the other way round ? Strange.... :)

Now that Mark has mentioned it, can we use weak induction to prove that every positive integer greater than 1 has a prime divisor?

By David Loeffler on Wednesday, May 08, 2002 - 08:57 am:

Well, no, because strong induction clearly also implies weak induction. They are equivalent.

By Chi K. Ho on Thursday, May 09, 2002 - 07:39 pm:

i understand now, thanks David.

[Editor: Probably the strong/weak distinction refers to the hypotheses.]