Initial Function in the Iterative Construction of the Cantor-Lebesgue Staircase Function

Question

In the Wikipedia of the Cantor function, one iterative construction for it is presented there:

Let $f_0(x)=x$ on $[0,1]$. For every positive integer $n$, define $$f_{n+1}(x)=\begin{cases} \frac{f_n(3x)}{2}, & x\in[0,\frac{1}{3}]; \\ \frac{1}{2}, & x\in(\frac{1}{3},\frac{2}{3}); \\ \frac{1+f_n(3x-2)}{2}, & x\in[\frac{2}{3},1]. \end{cases}$$ Then $(f_n)$ converges uniformly to the Cantor function on $[0,1]$.

I somewhat noticed a interesting statement at the end of that section:

Also the choice of starting function does not really matter, provided $f_0(0)=0$, $f_0(1)=1$ and $f_0$ is bounded.

where a "citation needed" link is attached to the end of this statement. Therefore, I began to seek for any explanations, but most of the papers (such as this classical survey) only take this fact for granted without any further justification. I have come up with one solution, which is attached below, and it would be nice if this would attract more beautiful and concise solutions.

Answer 1

Endow the space $C[0,1]$ of continuous functions on the unit interval with the maximum norm.

Consider the transformation $T:C[0,1] \to C[0,1]$ defined by

$$(Tf)(x)=\begin{cases} \frac{f (3x)}{2}, & x\in[0,\frac{1}{3}]; \\ \frac{1}{2}, & x\in(\frac{1}{3},\frac{2}{3}); \\ \frac{1+f(3x-2)}{2}, & x\in[\frac{2}{3},1] \,, \end{cases}$$ so that $f_{n+1}=Tf_n$ for all $n$. then it is easy to verify that $$\forall f,g \in C[0,1], \quad \; \|Tf-Tg\| =\frac12 \|f-g\|\,.$$

By https://en.wikipedia.org/wiki/Banach_fixed-point_theorem , for any choice of $f_0$, the iterates $f_n=T^nf_0$ converge uniformly to the unique fixed point of $T$. Ths fixed point is the Cantor function $G$ due to the choice $f_0(x)=x$.

Edit: As noticed by the OP, the proof above applies when $f_0$ is continuous. If all we know is that $f_0$ is bounded, the same argument can be used in the space $B[0,1]$ of bounded functions with the supremum norm.

Answer 2

Here we adopt the definition of the Cantor function $G$ again from this classical survey: For each $x\in[0,1]$ with ternary expansion $x=\sum_n{a_n(x)3^{-n}}$, let $N_x$ be the smallest index at which $a_n(x)=1$ and $N_x=\infty$ otherwise. Then $$G(x)=\frac{1}{2^{N_x}}+\frac{1}{2}\sum_{k=1}^{N_x-1}{\frac{a_n(x)}{2^n}}.$$ For convenience, we denote by $C$ the Cantor ternary set. If $x\in C$, then $a_n(x)\in\{0,2\}$ for all $n$ whence $N_x=\infty$ and $$G(x)=\frac{1}{2}\sum_{k=1}^{\infty}{\frac{a_n(x)}{2^n}}.$$

Now consider two cases:

• Suppose that $N_x=n<\infty$. Then we have $x=(0.a_1\ldots a_{n-1}1*)_3$ where $a_1,\ldots,a_{n-1}\in\{0,2\}$. We may now make the following observation: Let $k\in\mathbb{N}$ be an arbitrary index.

  • If $a_1=0$, then $x\le 1/3$ whence \begin{equation*} f_{k+1}(x)=\frac{f_k(3x)}{2}=\frac{f_k((0.a_2\ldots a_{n-1}1*)_3)}{2}. \end{equation*}

  • If $a_1=2$, then $x\ge 2/3$ whence \begin{equation*} f_{k+1}(x)=\frac{1+f_k(3x-2)}{2}=\frac{1+f_k((0.a_2\ldots a_{n-1}1*)_3)}{2}. \end{equation*}

  That is, we always have \begin{equation*} f_{k+1}(x)=\frac{1}{2}\cdot\frac{a_1}{2}+\frac{1}{2}\cdot f_k((0.a_2\ldots a_{n-1}1*)_3). \end{equation*} Then by an easy induction, we shall see that for all $k\ge n$, \begin{align*} f_k(x)&=\frac{1}{2}\sum_{k=1}^{n-1}{\frac{a_k}{2^k}}+\frac{1}{2^{n-1}}f_{k-n+1}((0.1*)_3) \\ &=\frac{1}{2}\sum_{k=1}^{n-1}{\frac{a_k}{2^k}}+\frac{1}{2^{n-1}}\cdot\frac{1}{2}=\frac{1}{2}\sum_{k=1}^{n-1}{\frac{a_k}{2^k}}+\frac{1}{2^n}=G(x), \end{align*} because $(0.1*)_3\in(1/3,2/3)$. Here the identity simply does not rely on the definition of $f_0$ actually but only the recursive definition. Note that here we can feel free to exclude the cases when $(0.1*)_3$ is $1/3$ or $2/3$, because $$\frac{1}{3}=(0.1000\ldots)_3=(0.0222\ldots)_3\quad\text{and}\quad\frac{2}{3}=(0.1222\ldots)_3=(0.2000\ldots)_3.$$

• Suppose that $N_x=\infty$, i.e., $x\in C$, the Cantor ternary set. By the observation above, for each $n\in\mathbb{N}$, we have \begin{align*} f_n(x)&=\frac{1}{2}\sum_{k=1}^{n}{\frac{a_k}{2^n}}+\frac{1}{2^n}f_0((0.a_{n+1}a_{n+2}\ldots)_3) \\ &\to G(x)+0=G(x). \tag{as $n\to\infty$} \end{align*} Here only the fact that $f_0$ is bounded is needed to ensure the last term tends to zero at the end.

Therefore, from the above discussion, we can see that the only essential property of $f_0$ is that $f_0$ is bounded on $[0,1]$. The original statement is justified here.

---

Update. Inspired by Yuval's answer, it seems that $f_0(0)=0$ and $f_0(1)=1$ are no longer needed to ensure the convergence. This is indeed true: By easy induction, we can see that

• $f_n(0)=2^{-n}f_0(0)\to 0$ as $n\to\infty$.

• The recursion here is $f_{n+1}(1)=[1+f_n(1)]/2$, so we indeed have $$f_n(1)=1+\frac{f_0(1)-1}{2^n}\to 1. \tag{as $n\to\infty$}$$