Results 1 to 2 of 2

Math Help - Strong Induction.

  1. #1
    Junior Member mremwo's Avatar
    Joined
    Oct 2010
    From
    Tampa, FL
    Posts
    53

    Strong Induction.

    How do you know when you can apply the induction hypothesis in strong induction??

    I understand how to get the base cases.
    And then assume that P(n).
    Then I understand that I need to prove P(n+1).

    What I don't understand is why you are able to apply the induction hypothesis. I know the reason is so that you can augment is to see the truth of P(n+1) but I don't understand when you are able to do so. Thanks

    *It would be helpful to show me via example of proving the existence of the "division algorithm," but anything is helpful. Thanks so much
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771
    Induction is a way of proving statements of the form "for all natural n, P(n)". To prove it, it is sufficient to prove P(0), called the base case, or basis, and the following statement: "for all natural n, P(n) implies P(n + 1)". The latter fact, called the induction step, is proved in a usual way, by fixing an arbitrary n and assuming P(n); from there one shows P(n + 1).

    As I said, there is nothing special about the way one proves the step. In general, one has to know how to prove facts of the form "for all n, Q(n)", "exists n, Q(n)", "R implies S", "R and S", "R or S", etc. Once this is known, showing the induction step is routine. Contrast this with proving the original statement "for all n, P(n)". The usual way of proving it is to fix some n and to show P(n). However, this is often impossible. Here comes induction as a special way of proving this fact.

    So the question boils down to, why the base case and the induction step guarantee that "for all n, P(n)" is true. Well, P(0) is shown in the base case. Further, one can instantiate universally quantified n in the induction step to any number. Thus, instantiating n to 0, we get "P(0) implies P(1)". Since P(0) is true, so is P(1). Next, instantiating n to 1 in the induction step, we get "P(1) implies P(2)". Since P(1) is true, so is P(2). Continuing in this way, one can show P(n) for each concrete number n.

    The situation you described, when the induction step is "for all n, P(n) implies P(n + 1)" is regular induction. Strong induction has the following induction step: "for all n, P(0) and P(1) and ... and P(n) together imply P(n + 1)".
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. STRONG induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 6th 2009, 08:23 PM
  3. Strong Induction help
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 7th 2009, 08:48 PM
  4. Strong induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 22nd 2008, 01:00 PM
  5. Strong Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 5th 2008, 08:50 AM

Search Tags


/mathhelpforum @mathhelpforum