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: Simple Proof by Induction Problem

  1. Aug 28, 2013 #1

    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.


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

    S_0 = \{\}
    S_i = \{0\} \bigcup \{s + \pi | s \in S_{i-1}\}
    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


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted