# Recurrence Relation for the nth Cantor Set

Wikipedia gives a recurrence relation for the $nth$ Cantor Set: $C_n = \frac{C_{n-1}}{3} \cup(\frac{2}{3}+\frac{C_{n-1}}{3})$.

http://en.wikipedia.org/wiki/Cantor_Set#Construction_and_Formula_of_the_ternary_set

How does one verify such a relation? I considered using induction, but I couldn't do much more than the base case with this one. Can someone provide on how to use induction with a recurrence relation?

-

## 2 Answers

$C_n$ isn’t a Cantor set; it’s the $n$-th approximation to the middle-thirds Cantor set, the $n$-th stage in the construction of the middle-thirds Cantor set. There really isn’t anything to verify: $$C_n=\frac{C_{n-1}}3\cup\left(\frac23+\frac{C_{n-1}}3\right)\tag{1}$$ is the recursion step of a definition whose initial step is $C_0=[0,1]$. The middle-thirds Cantor set is then defined to be $$C=\bigcap_{n\in\Bbb N}C_n\;,$$ and it’s at this point that there’s something to prove $-$ namely, that this $C$ has the various properties of the Cantor set.

For instance, in order to prove that $C$ is closed in $\Bbb R$, it suffices to show that each $C_n$ is closed. $C_0$ is certainly closed, so it suffices to show that the construction in $(1)$ preserves closedness. This isn’t hard: the map $\Bbb R\to\Bbb R:x\mapsto\frac{x}3$ is a homeomorphism, so if $C_{n-1}$ is closed, so is $\frac13C_{n-1}$. Similarly, translation by $\frac23$ is a homeomorphism, so $\frac23+\frac12C_{n-1}$ is closed. Finally, the union of two closed sets is closed, so $C_n$ is closed.

Similarly, one can use induction to show that $C_n\subseteq C_{n-1}$ for each $n\in\Bbb N$. It’s easy to verify directly that $C_1\subseteq C_0$. Now assume that $C_n\subseteq C_{n-1}$ for some $n\in\Bbb N$: $$C_n=\frac{C_{n-1}}3\cup\left(\frac23+\frac{C_{n-1}}3\right)\subseteq C_{n-1}\;.$$ Then

\begin{align*} C_{n+1}&=\frac{C_n}3\cup\left(\frac23+\frac{C_n}3\right)\\ &=\frac13\left(\frac{C_{n-1}}3\cup\left(\frac23+\frac{C_{n-1}}3\right)\right)\cup\left(\frac23+\frac13\left(\frac{C_{n-1}}3\cup\left(\frac23+\frac{C_{n-1}}3\right)\right)\right)\\ &\subseteq\frac13C_{n-1}\cup\left(\frac23+\frac13C_{n-1}\right)\\ &=C_n\;, \end{align*}

as desired.

With more work one can use this definition to show that $C$ contains no non-trivial interval.

Added: To see that this construction not only gives a Cantor set but gives the familiar middle-thirds Cantor set, look at the numbers in $[0,1]$ in terms of their ternary expansions. First, $$C_0=\left\{\sum_{n\ge 1}\frac{a_n}{3^n}:a_n\in\{0,1,2\}\text{ for }n\ge 1\right\}\;.$$ For convenience let me write $0.a_1a_2a_3\dots$ instead of $\sum_{n\ge 1}\frac{a_n}{3^n}$. Then $C_0$ contains all of the ternary expansions $0.a_1a_2a_3\dots$. Multiplying by $\frac13$ just moves every digit one place to the right, changing $0.a_1a_2a_3\dots$ to $0.0a_1a_2a_3\dots$, and adding $\frac23$ to each of these numbers gives us all of the ternary expansions of the form $0.2a_1a_2a_3\dots$. In other words, $C_1$ consists of the numbers in $[0,1]$ with ternary expansions beginning with $0$ or $2$: we’ve stripped out those numbers that have only ternary expansions beginning with $1$, i.e., those in $\left(\frac13,\frac23\right)$.

At each stage the recursion in $(1)$ takes the numbers in $C_{n-1}$, shifts their ternary expansions one place to the right, and inserts a leading $0$ or $2$. Thus, the numbers in $C_2$ are those with ternary expansions whose first two digits are either $0$ or $2$, and in general $C_n$ contains those numbers in $[0,1]$ with ternary expansions whose first $n$ digits are all either $0$ or $2$.

This is exactly the same thing that happens when we remove the open middle thirds in the other recursive construction.

-
But how do we verify that (1) is the recursion step for any natural number k greater than 1? My question is how to verify (1). –  The Substitute Jul 3 '12 at 22:14
@Broseph: There’s nothing to verify: it’s a definition. –  Brian M. Scott Jul 3 '12 at 22:19
@ Brian: But how do we know this definition gives the desired nth set which is derived from the $n-1$st set by removing the middle third intervals. Certainly the processes of removing middle 3rd intervals and the recursive relation are different even though they produce the same set. –  The Substitute Jul 3 '12 at 22:23
@Broseph: We don’t actually need to know that: we need only prove that $C$, as defined here, has the desired properties. However, it’s not at all hard to prove if you look at the ternary expansions; I’ll add that to my answer, since it’s a little long for a comment. Hang on a few minutes. –  Brian M. Scott Jul 3 '12 at 22:29
That clears everything up. Thank you for the nice answer(s)! –  The Substitute Jul 3 '12 at 22:46

Instead of considering the $n^{th}$ stage of the Cantor set to be the $n-1^{st}$ with the middle third of each segment removed, it uses the alternate construction of taking the $n-1^{st}$ stage, shrinking by a factor of $3$, and duplicating the shrunk version in the interval $[\frac 23,1]$. If you take a point that is in $C_{n-1}$ it has a ternary expansion $0.a_1a_2a_3\ldots$ where the first $n-1$ digits are $0$ or $2$. For $C_n$ it is taken to $0.0a_1a_2a_3\ldots$ and $0.2a_1a_2a_3\ldots$, so each one has the first $n$ digits either $0$ or $2$.

-