1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Strong Induction

  1. Jun 28, 2010 #1
    I understand weak induction but I'm confused on strong induction. Can someone give me a simple example where you would use strong induction and not weak?
     
  2. jcsd
  3. Jun 28, 2010 #2
    Proving that any natural number > 1 can be expressed as the product of (one or more) primes.
     
  4. Jun 28, 2010 #3

    disregardthat

    User Avatar
    Science Advisor

    Strong induction is characterized by that instead of proving P(k) --> P(k+1), where P(n) is a proposition for a number n, we rather prove that ( P(1) and P(2) and ... and P(k) )--> P(k+1). It is stronger in the sense that we use more information for the inductive step.

    For example; if you want to prove a specific formula for a difference equation, say [tex]x_{n-2}+x_{x-1}=x_n[/tex], by induction, you will need, for the inductive step, that both [tex]x_{k-1}[/tex] and [tex]x_{k}[/tex] satisfy the formula in order to prove the formula for [tex]x_{k+1}[/tex]. In other words; you will need P(k-1) and P(k) to prove P(k+1), where P(n) is the proposition that [tex]x_n[/tex] satisfies the formula.
     
  5. Jun 28, 2010 #4
    So is this pretty much like saying you have more than one base case? Specifically, you have as many base cases as there are variables?
     
  6. Jun 29, 2010 #5

    disregardthat

    User Avatar
    Science Advisor

    The base case P(1) must of course be proven. But no, you don't need more than one base case. You'd think so, but you can see it is 'taken care of' by the inductive step. The general proof of the inductive step must be valid for n = 2, so another base case need not be established, but care must be taken. I.e. in the inductive step, you assume ( P(1) and P(2) and ... and P(k) ), but you must consider the possibility k = 1; in which case you do not have P(k) and P(k-1), but only P(k). This can however easily be verified by a direct proof.

    Other examples would perhaps require ( P(1) and P(2) and ... P(k) ) to prove P(k+1), and not just ( P(k-1) and P(k) ) as in this example.

    Strong induction can be proven logically equivalent to weak induction, so it's not stronger in that sense.
     
    Last edited: Jun 29, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook