# Simple Proof by Induction Problem

1. Aug 28, 2013

### CuppoJava

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

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

3. The attempt at a solution

I started by converting the problem to the following form:

$\forall i > 0, 0 \in S_i$
$\forall s \in S_i, s + \pi \in S_{i + 1}$
Show that $\forall s \in S_i, s \in S_{i + 1}$

But I don't know what to do next.

2. Aug 28, 2013

### haruspex

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. Aug 28, 2013

### CuppoJava

... therefore $y$ is in $S_n$ according to the assumed hypothesis.
Therefore $y + 1 = x$ is in $S_{n+1}$.
Therefore $S_i \subseteq S_{i+1}$ by induction.

Thank you!
-Patrick