Difference between Strong Induction and Mathematical Induction?

[phillyolly]

Homework Statement

Explain the difference between The principle of Mathematical Induction and The principle of Strong Induction. One is easier than the other. Why?

Homework Equations

The Attempt at a Solution

My book says that they are in fact identical. Proofs are almost the same...

 

[lanedance]

have a look here
http://en.wikipedia.org/wiki/Mathematical_induction#Complete_induction

 

[phillyolly]

Is that true that Mathematical Induction is easier to use VS Complete (or Strong) Induction?

 

[lanedance]

i've only really used the basic induction... but I suppose it would depend on the problem though

 

[Raskolnikov]

Depends on how you define "easy." If you read the section on the wiki article that lanedance posted, you'll see that Complete Induction actually makes many proofs (e.g. theorems based on Fibonacci numbers where recursion is necessary) much 'easier.' It makes sense since recursion falls back onto previous cases, and strong induction already assumes these to be true. I'd get comfortable with both types of induction if I were you.

 

[HallsofIvy]

With simple induction you use "if p(k) is true then p(k+1) is true" while in strong induction you use "if p(i) is true for all i less than or equal to k then p(k+1) is true", where p(k) is some statement depending on the positive integer k.

They are NOT "identical" but they are equivalent.

It is easy to see that if simple induction is true then strong induction is true: if you know that statement p(i) is true for all i less than or equal to k, then you know that it is true, in particular, for i= k and can use simple induction.

It is harder to prove, but still true, that if strong induction is true, then simple induction is true. That is what we mean by "equivalent".