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: Weak induction is equivalent to strong induction

  1. Sep 8, 2011 #1
    1. The problem statement, all variables and given/known data

    Prove that weak induction is equivalent to strong induction.

    2. Relevant equations

    To prove this...we assume weak induction. That is

    (i) 1 [itex]\in[/itex] S
    (ii) n[itex]\in[/itex] S [itex]\Rightarrow[/itex] n+1 [itex]\in[/itex] S for all n in N


    3. The attempt at a solution

    So to prove strong induction we need to prove the following:
    (i) 1 [itex]\in[/itex] S
    This is given by our assumption of weak induction.
    (ii) {1....n} [itex]\in[/itex] is a subset of S.
    SInce we know 1 is in S, we can make 2...n by 1+1, 1+1+1, 1+....+1 (n times)
    (iii) if (ii) is true than n+1 is in S.
    I think this is true because our assumption guaranteed this.

    This is a rough sketch of what I wan to say. Am I on the right track.
     
  2. jcsd
  3. Sep 9, 2011 #2
    So assume weak induction, that is:

    If
    (i) [itex]1\in S[/itex]
    (ii) [itex]n\in S~\Rightarrow~n+1\in S[/itex]
    then [itex]S=\mathbb{N}[/itex].

    You need to prove that strong induction holds. That is, you assume that
    (a) [itex]1\in S[/itex]
    (b) [itex]\{1,...,n\}\in S~\Rightarrow~n+1\in S[/itex].
    You need to prove from (a) and (b) that [itex]S=\mathbb{N}[/itex]. You don't need to prove (a) and (b), they are given.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook