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!

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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Weak induction is equivalent to strong induction
  1. Strong Induction (Replies: 8)

Loading...