Results 1 to 3 of 3

Math Help - Induction

  1. #1
    Newbie
    Joined
    May 2011
    Posts
    3

    Induction

    Hi there,
    I need help with proving "weak induction--->string induction" using weak induction
    Where to start?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771
    Weak induction for natural numbers: P(0) -> ∀x (P(x) -> P(x+1)) -> ∀x P(x).
    Strong induction for natural numbers: ∀x ((∀y < x Q(y)) -> Q(x)) -> ∀x Q(x).

    To prove strong induction for a given property Q, apply weak induction where P(x) is ∀y < x Q(y).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2011
    Posts
    3
    We want to prove that
    P(0) and
    (forall k. (forall m. m < k+1 implies P(m)) implies P(k+1))
    implies
    forall n. P(n)

    The proof of this by mathematical induction won't go through unless
    we strengthen what we're trying to prove to the following

    P(0) and
    (forall k. (forall m. m < k+1 implies P(m)) implies P(k+1))
    implies
    forall n. forall i. i < n implies P(i)

    Now for the proof by mathematical induction on n.
    Base case, n=0:
    We need to show that forall i. i < 0 implies P(0).
    This is vacuosly true because there is no natural number i such that i < 0.

    Induction step:
    The induction hypothesis is forall i. i < n implies P(i).
    We need to show that forall i. i < n+1 implies P(i).
    So we pick an arbitrary i where i < n+1 and need to prove P(i).
    We consider the following two cases.
    Case i < n:
    Then by the induction hypothesis we have P(i).
    Case i = n:
    We consider two further subcases:
    Case n = 0:
    We have P(i) from the assumption P(0).
    Case n > 0:
    There is some k such that n = k + 1.
    With this and the induction hypothesis we have forall i<k+1. P(i).
    We can then apply the step assumption to get P(k+1), which is P(i).
    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. Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 11th 2010, 02:08 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 19th 2008, 05:12 PM

Search Tags


/mathhelpforum @mathhelpforum