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!

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