Proof by Induction: Recursively Defined Sequential Set

Question

We recursively define a sequence of subsets of $\mathbb Z$ as follows:

Let $S_0=\{0\}$, and let $S_{n+1}=\{2m: m \in S_n\} \cup \{2m+1: m \in S_n\}$ for all $n \geq 0$.

(So $S_1=\{0,1\}$, $S_2=\{0,1,2,3\}$,...)

I've figured out part 1, but I'd greatly appreciate it if someone could help me solve parts 2 and 3!

1. Find $S_3$.

My solution: $S_3=\{0,1,2,3,4,5,6,7\}$

2. I claim that $7 \in S_n$ for all $n \geq 3$. It turns out to be easier to prove the following stronger statement: "$\{0,1,3,7\} \subseteq S_n$ for all $n \geq 3$". Prove by induction.

At first I thought I could use $\{2m+1: m \in S_{n-1}\}\subseteq S_n$ with a basis of $n \geq 3$ as my conjecture, but I realized this doesn't work because the statement also claims that $0$ is an element.

3. Now consider the infinite union, $\bigcup_{n=0}^{\infty} S_{n}=S_0 \cup S_1 \cup S_2 \cup ...$ Find this set (List its elements, nicely, possibly using "..."). Briefly explain why your answer is correct.

I have no clue how to approach this part.

Does anyone have any ideas? Thanks in advance!

Answer 1

We wanna proof that:

$$S_n= \{0,1,...,2^n-1 \}$$

If $n=1$:

$$S_1=\{0,1\}$$

Let's suppose it's true for $n$ :

$$S_n= \{0,1,...,2^n-1 \}$$

Now divide $S_{n+1}$ in two sets, one containing even numbers $E_{n+1}$ and one containing odd numbers $O_{n+1}$,by the definiction of the set:

$$E_{n+1}=\{2\times0,2\times1,...,2\times(2^n-1) \}=\{0,2,4,6,...,2^{n+1}-2\}$$

$$O_{n+1}=\{2\times0+1,2\times1+1,...,2\times(2^n-1)+1 \}=\{1,3,5,7,...,2^{n+1}-1\}$$

So:

$$S_{n+1}=E_{n+1}\cup O_{n+1}=\{0,1,...,2^{n+1}-1 \}$$

This concludes the proof and implies that:

$$\bigcup_{i=0}^{\infty} S_i=\Bbb{N}$$

:)

Answer 2

Hint: Try proving by induction the following $$S_n=\{0,1,...,2^n-1\}$$