Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Difference between Strong Induction and Mathematical Induction?

  1. Aug 25, 2010 #1
    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...
  2. jcsd
  3. Aug 25, 2010 #2


    User Avatar
    Homework Helper

  4. Aug 25, 2010 #3
    Is that true that Mathematical Induction is easier to use VS Complete (or Strong) Induction?
  5. Aug 25, 2010 #4


    User Avatar
    Homework Helper

    i've only really used the basic induction... but I suppose it would depend on the problem though
  6. Aug 25, 2010 #5
    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.
  7. Aug 25, 2010 #6


    User Avatar
    Science Advisor

    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".
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook