1. Not finding help here? Sign up for a free 30min 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!

Simple Proof by Induction Problem

  1. Aug 28, 2013 #1
    Hi,

    I devised this problem for myself as part of a bigger question that I'm working on, and am having trouble solving it. I think it involves a nested induction proof but I am not sure how to start. A tip on how to begin would be much appreciated.

    Thanks
    -Patrick

    1. The problem statement, all variables and given/known data

    [itex]
    S_0 = \{\}
    [/itex]
    [itex]
    S_i = \{0\} \bigcup \{s + \pi | s \in S_{i-1}\}
    [/itex]
    Show that [itex] S_i \subseteq S_{i+1} [/itex] for all [itex]i[/itex].


    3. The attempt at a solution

    I started by converting the problem to the following form:

    [itex]\forall i > 0, 0 \in S_i[/itex]
    [itex]\forall s \in S_i, s + \pi \in S_{i + 1}[/itex]
    Show that [itex] \forall s \in S_i, s \in S_{i + 1} [/itex]

    But I don't know what to do next.
     
  2. jcsd
  3. Aug 28, 2013 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Suppose true up to some i = n. Let x be in Sn. You want to show it is in Sn+1. Trivial if x = 0, otherwise x = y+π for some y in Sn-1. By the inductive hypothesis, since y is in Sn-1 it is also in ...?
     
  4. Aug 28, 2013 #3
    ... therefore [itex]y[/itex] is in [itex]S_n[/itex] according to the assumed hypothesis.
    Therefore [itex] y + 1 = x [/itex] is in [itex]S_{n+1}[/itex].
    Therefore [itex] S_i \subseteq S_{i+1} [/itex] by induction.

    Thank you!
    -Patrick
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Simple Proof by Induction Problem
  1. Simple Induction Proof (Replies: 2)

Loading...