Simple Proof by Induction Problem

  • Thread starter CuppoJava
  • Start date
  • #1
CuppoJava
24
0
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

Homework Statement



[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].


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.
 

Answers and Replies

  • #2
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
38,833
8,219
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 ...?
 
  • #3
CuppoJava
24
0
... 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
 

Suggested for: Simple Proof by Induction Problem

  • Last Post
Replies
7
Views
480
  • Last Post
Replies
4
Views
279
  • Last Post
Replies
4
Views
617
Replies
6
Views
299
  • Last Post
Replies
23
Views
375
Replies
8
Views
381
  • Last Post
Replies
2
Views
840
Replies
4
Views
275
  • Last Post
Replies
3
Views
944
Top