Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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})$.

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?

share|cite|improve this question
up vote 4 down vote accepted

$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.

share|cite|improve this answer
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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.