1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    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

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

Have something to add?
Draft saved Draft deleted

Similar Threads - Simple Proof Induction Date
Simple Induction Proof Sep 13, 2010
Help with simple proof by mathematical induction May 2, 2010
Simple inequality proof by induction Mar 28, 2010
Simple proof of inequality by induction Oct 12, 2009
Two Simple Induction Proofs Jan 21, 2008