• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Difference between Strong Induction and Mathematical Induction?

  • Thread starter phillyolly
  • Start date
1. The problem statement, all variables and given/known data

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


2. Relevant equations



3. The attempt at a solution

My book says that they are in fact identical. Proofs are almost the same...
 
Is that true that Mathematical Induction is easier to use VS Complete (or Strong) Induction?
 

lanedance

Homework Helper
3,304
2
i've only really used the basic induction... but I suppose it would depend on the problem though
 
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

Science Advisor
41,625
823
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".
 

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top