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?
 A: $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.
A: 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$.
