How to prove this closed formula for Cantor set?

Question

Let $C_0=[0,1]$ and $C_{n+1} = \dfrac{C_n}{3} \bigcup\left(\dfrac{2}{3}+\dfrac{C_n}{3}\right)$.

Theorem: $$C_n=\bigcap_{m=0}^{n}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k}{3^m},\frac{2k+1}{3^m}\right]$$

I have tried to prove this assertion by induction on $n$, but to no avail. I am stuck at inductive step.

Please shed me some light to accomplish the proof. Thank you so much!

---

My attempt:

The formula is trivially true for $n=0$. Let it hold for $n$.

$$C_{n+1}=\frac{C_n}{3} \cup\left(\frac{2}{3}+\frac{C_n}{3}\right)$$

$$=\left(\frac{1}{3} \bigcap_{m=0}^{n}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k}{3^m},\frac{2k+1}{3^m}\right]\right) \cup \left(\frac{2}{3}+\frac{1}{3} \bigcap_{m=0}^{n}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k}{3^m},\frac{2k+1}{3^m}\right] \right)$$

$$=\left(\bigcap_{m=0}^{n}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k}{3^{m+1}},\frac{2k+1}{3^{m+1}}\right]\right) \cup \left(\bigcap_{m=0}^{n}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k+2.3^m}{3^{m+1}},\frac{2k+2.3^m+1}{3^{m+1}}\right]\right)$$

$$=\left(\bigcap_{m=0}^{n}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k}{3^{m+1}},\frac{2k+1}{3^{m+1}}\right]\right) \cup \left(\bigcap_{m=0}^{n}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2(k+3^m)}{3^{m+1}},\frac{2(k+3^m)+1}{3^{m+1}}\right]\right)$$

$$=\left(\bigcap_{m=0}^{n}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k}{3^{m+1}},\frac{2k+1}{3^{m+1}}\right]\right) \cup \left(\bigcap_{m=0}^{n}\bigcup_{k=3^m}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor+3^m}\left[\frac{2k}{3^{m+1}},\frac{2k+1}{3^{m+1}}\right]\right)$$

Answer 1

After several hours of thinking, I have figured out a proof and posted it here as an answer.

---

Lemma: $$2 . \left\lfloor \frac{3^{m}}{2}\right\rfloor = 3^m-1$$

Proof:

We prove this assertion by induction on $n$. The statement is trivially true for $n=0$. Let it hold for $n$.

$2 . \left\lfloor \dfrac{3^{m+1}}{2}\right\rfloor = 2 . \left\lfloor \dfrac{2.3^{m}+3^m}{2}\right\rfloor=2 . \left\lfloor 3^m+ \dfrac{3^m}{2}\right\rfloor=2\left(3^m+\left\lfloor \dfrac{3^{m}}{2}\right\rfloor\right)=$ $2.3^m+2 . \left\lfloor \dfrac{3^{m}}{2}\right\rfloor$ $=2.3^m+(3^m-1)=3^{m+1}-1$. This completes the proof.

The formula is trivially true for $n=0$. Let it hold for $n$.

$\begin{align}C_{n+1} &=\frac{C_n}{3} \cup\left(\frac{2}{3}+\frac{C_n}{3}\right)\\ &=\left(\frac{1}{3} \bigcap_{m=0}^{n}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k}{3^m},\frac{2k+1}{3^m}\right]\right) \cup \left(\frac{2}{3}+\frac{1}{3} \bigcap_{m=0}^{n}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k}{3^m},\frac{2k+1}{3^m}\right] \right)\\ &=\left(\bigcap_{m=0}^{n}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k}{3^{m+1}},\frac{2k+1}{3^{m+1}}\right]\right) \cup \left(\bigcap_{m=0}^{n}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k+2.3^m}{3^{m+1}},\frac{2k+2.3^m+1}{3^{m+1}}\right]\right)\\ &=\left(\bigcap_{m=0}^{n}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k}{3^{m+1}},\frac{2k+1}{3^{m+1}}\right]\right) \cup \left(\bigcap_{m=0}^{n}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2(k+3^m)}{3^{m+1}},\frac{2(k+3^m)+1}{3^{m+1}}\right]\right)\\ &=\left(\bigcap_{m=0}^{n}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k}{3^{m+1}},\frac{2k+1}{3^{m+1}}\right]\right) \cup \left(\bigcap_{m=0}^{n}\bigcup_{k=3^m}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor+3^m}\left[\frac{2k}{3^{m+1}},\frac{2k+1}{3^{m+1}}\right]\right)\\ &=\left(\bigcap_{t=1}^{n+1}\bigcup_{k=0}^{\left\lfloor \frac{3^{t-1}}{2}\right\rfloor}\left[\frac{2k}{3^{t}},\frac{2k+1}{3^{t}}\right]\right) \cup \left(\bigcap_{t=1}^{n+1}\bigcup_{k=3^{t-1}}^{\left\lfloor \frac{3^{t-1}}{2}\right\rfloor+3^{t-1}}\left[\frac{2k}{3^{t}},\frac{2k+1}{3^{t}}\right]\right) \text{ Let }t=m+1\\ &=\left(\bigcap_{m=1}^{n+1}\bigcup_{k=0}^{\left\lfloor \frac{3^{m-1}}{2}\right\rfloor}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right]\right) \cup \left(\bigcap_{m=1}^{n+1}\bigcup_{k=3^{m-1}}^{\left\lfloor \frac{3^{m-1}}{2}\right\rfloor+3^{m-1}}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right]\right) \text{ Let }m=t\end{align}$

We have some observations.

1.

$\bigcap_{m=1}^{1}\bigcup_{k=0}^{\left\lfloor \frac{3^{m-1}}{2}\right\rfloor}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right]=\bigcup_{k=0}^{0}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right]=\left[0,\frac{1}{3}\right]$.

2.

$\frac{1}{3}<\frac{2k}{3^{m}}$ and $\frac{2k+1}{3^{m}}<\frac{2}{3}$ for all $\left\lfloor \frac{3^{m-1}}{2}\right\rfloor +1\le k \le 3^{m-1}-1$. Then $\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right] \subsetneq \left(\frac{1}{3},\frac{2}{3}\right)$ for all $\left\lfloor \frac{3^{m-1}}{2}\right\rfloor +1\le k \le 3^{m-1}-1$. It follows that $\bigcup_{k=\left\lfloor \frac{3^{m-1}}{2}\right\rfloor +1}^{3^{m-1}-1}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right] \subsetneq \left(\frac{1}{3},\frac{2}{3}\right)$ and thus $\left(\bigcap_{m=1}^{1}\bigcup_{k=0}^{\left\lfloor \frac{3^{m-1}}{2}\right\rfloor}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right]\right) \cap \left( \bigcup_{k=\left\lfloor \frac{3^{m-1}}{2}\right\rfloor +1}^{3^{m-1}-1}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right]\right) =\emptyset$.

3.

From 1. and 2., we get

$\begin{align}\bigcap_{m=1}^{n+1}\bigcup_{k=0}^{\left\lfloor \frac{3^{m-1}}{2}\right\rfloor}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right] &= \bigcap_{m=1}^{n+1} \left[\left( \bigcup_{k=0}^{\left\lfloor \frac{3^{m-1}}{2}\right\rfloor}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right] \right) \cup \left(\bigcup_{k=\left\lfloor \frac{3^{m-1}}{2}\right\rfloor+1}^{3^{m-1}-1}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right] \right) \right]\\&=\bigcap_{m=1}^{n+1}\bigcup_{k=0}^{3^{m-1}-1}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right]\end{align}$

4.

$2 \left(\left\lfloor \frac{3^{m-1}}{2}\right\rfloor+3^{m-1} \right)=2 \left(\left\lfloor \frac{3^{m-1}}{2}\right\rfloor\right)+2.3^{m-1}=(3^{m-1}-1)+2.3^{m-1}=3.3^{m-1}-1=$ $3^m-1=2 . \left\lfloor \frac{3^{m}}{2}\right\rfloor$. Hence $\left\lfloor \frac{3^{m-1}}{2}\right\rfloor+3^{m-1}=\left\lfloor \frac{3^{m}}{2}\right\rfloor$.

As a result,

$$C_{n+1}= \left(\bigcap_{m=1}^{n+1}\bigcup_{k=0}^{3^{m-1}-1}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right] \right) \cup \left(\bigcap_{m=1}^{n+1}\bigcup_{k=3^{m-1}}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right]\right)$$

Let $I_m^k=\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right]$.

$$C_{n+1}= \left(\bigcap_{m=1}^{n+1}\bigcup_{k=0}^{3^{m-1}-1} I_m^k \right) \cup \left(\bigcap_{m=1}^{n+1}\bigcup_{k=3^{m-1}}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor} I_m^k \right)$$

$\frac{2k+1}{3^{m}}<\frac{2}{3}$ for all $k \le 3^{m-1}-1$ and $\frac{2}{3} \le \frac{2k}{3^{m}}$ for all $k \ge 3^{m-1}$ $\implies$ $\left(\bigcup_{k=0}^{3^{m_1-1}-1} I_m^k\right) \cap \left( \bigcup_{k=3^{m_2-1}}^{\left\lfloor \frac{3^{m_2}}{2}\right\rfloor} I_m^k \right) =\emptyset$ for all $m_1,m_2 \le n+1$.

Lemma: Let $I_n= \{i\in\Bbb N \mid 0 \le i \le n\}$ and $(A_i \mid i\in I_n)$, $(B_i \mid i\in I_n)$ be collections of nonempty sets such that $A_i \cap B_j =\emptyset$ for all $i,j\in I_n$. Then $$\left(\bigcap_{i\in I_n} A_i \right) \cup \left(\bigcap_{i\in I_n} B_i\right)= \bigcap_{i\in I_n} (A_i\cup B_i)$$

Proof: It is easy to verify this lemma.

We apply this lemma for $C_{n+1}$ and get $$C_{n+1}=\bigcap_{m=1}^{n+1}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right]$$

First, $C_{n+1} \subseteq [0,1]$ and thus $C_{n+1}=C_{n+1} \cap [0,1]$.

Second, $\bigcap_{m=0}^{0}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right]=\bigcup_{k=0}^{0}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right] =[0,1]$.

As a result,

$\begin{align}C_{n+1}&=\left(\bigcap_{m=1}^{n+1}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right]\right) \cap [0,1]\\&= \left(\bigcap_{m=1}^{n+1}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right]\right) \cap \left( \bigcap_{m=0}^{0}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right] \right)\\&=\bigcap_{m=0}^{n+1}\bigcup_{k=0}^{\left\lfloor \frac{3^{m}}{2}\right\rfloor}\left[\frac{2k}{3^{m}},\frac{2k+1}{3^{m}}\right]\end{align}$

This completes the proof.

Answer 2

Notice that

$$\bigcap_{m=0}^{n+1}\bigcup_{k=0}^{\lfloor 3^m/2\rfloor}\left[\frac{2k}{3^m},\frac{2k+1}{3^m}\right]=\left(\bigcap_{m=0}^{n}\bigcup_{k=0}^{\lfloor 3^m/2\rfloor}\left[\frac{2k}{3^m},\frac{2k+1}{3^m}\right]\right)\cap \bigcup_{k=0}^{\lfloor 3^{n+1}/2\rfloor}\left[\frac{2k}{3^{n+1}},\frac{2k+1}{3^{n+1}}\right]\\=C_n\cap \bigcup_{k=0}^{\lfloor 3^{n+1}/2\rfloor}\left[\frac{2k}{3^{n+1}},\frac{2k+1}{3^{n+1}}\right]$$

We may notice that if we divide the interval $[0,1]$ into $3^{n+1}$ parts we will get $[0,\frac{1}{3^{n+1}}],\ldots,[\frac{3^{n+1}-1}{3^{n+1}},1]$.

$\bigcup_{k=0}^{\lfloor 3^{n+1}/2\rfloor}\left[\frac{2k}{3^{n+1}},\frac{2k+1}{3^{n+1}}\right]$ is just taking the even parts of the list together, notice that $C_{n+1}\subseteq \bigcup_{k=0}^{\lfloor 3^{n+1}/2\rfloor}\left[\frac{2k}{3^{n+1}},\frac{2k+1}{3^{n+1}}\right]\cap C_n$, now notice that the even intervals of this stage are always the first and last thirds of the even intervals of the previous stages, so if $x\in C_n$, it had to be in the form $0.d_1d_2\ldots_3$ where $i\in \{1,2,\ldots, n-1\}$ implies $d_i\in\{0,2\}$, or in other words $x\in[0.d_1\ldots d_{n-1}0_3,0.d_1\ldots d_{n-1}2_3]$, $d_n$ will be $0$ on the first third and $2$ on the last third, so $C_n \cap \bigcup_{k=0}^{\lfloor 3^{n+1}/2\rfloor}\left[\frac{2k}{3^{n+1}},\frac{2k+1}{3^{n+1}}\right]\subseteq C_{n+1}$