Proof by Induction: Recursively Defined Sequential Set

[crdavis1219]

We recursively define a sequence of subsets of [MATH]\mathbb Z[/MATH] as follows:
Let [MATH]S_0=\{0\}[/MATH], and let [MATH]S_{n+1}=\{2m: m \in S_n\} \cup \{2m+1: m \in S_n\}[/MATH] for all [MATH]n \geq 0[/MATH]. (So [MATH]S_1=\{0,1\}[/MATH], [MATH]S_2=\{0,1,2,3\}[/MATH],...)
1. Find [MATH]S_3[/MATH]. This part I have already solved. My solution: [MATH]S_3=\{0,1,2,3,4,5,6,7\}[/MATH]2. I claim that [MATH]7 \in S_n[/MATH] for all [MATH]n \geq 3[/MATH]. It turns out to be easier to prove the following stronger statement: "[MATH]\{0,1,3,7\} \subseteq S_n[/MATH] for all [MATH]n \geq 3[/MATH]". Prove by induction.
3. Now consider the infinite union, [MATH]\bigcup_{n=0}^{\infty} S_{n}=S_0 \cup S_1 \cup S_2 \cup ...[/MATH] Find this set (List its elements, nicely, possibly using "..."). Briefly explain why your answer is correct.

I'd greatly appreciate it if someone could help me solve parts 2 and 3!

 

[Dr.Peterson]

What is your answer to part 1? (It looks like you started to write it, but didn't.)

Then please show how far you got in the inductive proof. We can't tell what help you need without that. (And please read and follow our submission guidelines.)

 

[pka]

We recursively define a sequence of subsets of [MATH]\mathbb Z[/MATH] as follows:
Let [MATH]S_0=\{0\}[/MATH], and let [MATH]S_{n+1}=\{2m: m \in S_n\} \cup \{2m+1: m \in S_n\}[/MATH] for all [MATH]n \geq 0[/MATH]. (So [MATH]S_1=\{0,1\}[/MATH], [MATH]S_2=\{0,1,2,3\}[/MATH],...)
1. Find [MATH]S_3[/MATH]. This part I have already solved. My solution: [MATH]S_3=\{0,1,2,3,4,5,6,7\}[/MATH]2. I claim that [MATH]7 \in S_n[/MATH] for all [MATH]n \geq 3[/MATH]. It turns out to be easier to prove the following stronger statement: "[MATH]\{0,1,3,7\} \subseteq S_n[/MATH] for all [MATH]n \geq 3[/MATH]". Prove by induction.
3. Now consider the infinite union, [MATH]\bigcup_{n=0}^{\infty} S_{n}=S_0 \cup S_1 \cup S_2 \cup ...[/MATH] Find this set (List its elements, nicely, possibly using "..."). Briefly explain why your answer is correct.

Can you use induction to show that \(\displaystyle (\forall n)[S_{n}\subseteq S_{n+1}]~?\)

 

[HallsofIvy]

I would first conjecture that \(\displaystyle S_n\) contains all the non-negative integers up to \(\displaystyle 2^n- 1\) and try to prove that by induction.

When n= 0 \(\displaystyle S_0= {0}\) which is the set of all non-negative integers up to \(\displaystyle 2^0- 1= 1- 1= 0\) so the base case is correct.

Suppose that, for some n= k, \(\displaystyle S_k= \{0, 1, 2, \cdot\cdot\cdot, 2^k- 2, 2^k- 1\}\). Then \(\displaystyle S_{k+1}\) all numbers of the form 2m with m in \(\displaystyle S_k\). That is, it contains \(\displaystyle \{0, 2, 4, \cdot\cdot\cdot, 2^{k+1}- 4, 2^{k+ 2}- 2\}\). It also contains all numbers of the form 2m+ 1 with m in \(\displaystyle S_k\). That is, it contains \(\displaystyle \{1, 3, \cdot\cdot\cdot, 2^{k+ 1}- 3, 2^{k+1}- 1\}\). Taking the union of those two sets we get \(\displaystyle \{0, 1, 2, 3, 4, \cdot\cdot\cdot, 2^{k+1}- 4, 2^{k+1}- 3, 2^{k+1}- 2, 2^{k+ 1}- 1\}\) which is, indeed, the set of all non-negative integers up to \(\displaystyle 2^{k+1}- 1\).