## An integral over a nested function

This was a case study in a brilliant problem posted by a very inexperienced M.SE user. There were 2 answers offered to this problem: mine and another. The other was very wrong, its wrongness blindingly so; yet, the user chose to accept this wrong answer. This act of course in M.SE has the effect of garnering multiple upvotes for this correct answer – even a plea from another user to reconsider. But, nonetheless…it makes this blog because it is a fairly intricate problem. Here it is:

Define

$$h(x)= \begin{cases}\\ 2x & \left(0\leq x\leq \frac{1}{3}\right)\\ \frac{1}{2}x+\frac{1}{2} & \left(\frac{1}{3}\lt x \leq 1\right) \end{cases}$$

Further define $h_2(x)=h(h(x)), h_3(x)=h_2(h(x)),\cdots, h_{n+1}(x)=h_n(h(x))$. Determine

$$\int_0^1 dx \, h_n(x)$$

First, it helps to plot the first few $h_n$:

Playing around with the patterns of this recursion, I get the following:

$$h_n(x) = \begin{cases} \\2^n x, & 0 \lt x \lt \frac{1}{3 \cdot 2^{n-1}}\\2^{n-2 m} x + \left (1-\frac{1}{2^m}\right ),&\frac{1}{3 \cdot 2^{n-m}} \lt x \lt \frac{1}{3 \cdot 2^{n-m-1}} \\ \frac{1}{2^n} x +\left (1-\frac{1}{2^n}\right ),&\frac{1}{3} \lt x \lt 1 \end{cases}$$

where $m \in \{1,2,\ldots,n-1\}$. You can verify this is true by induction, using $h_{n+1}(x) = h(h_n(x))$. (I leave this to the reader.)

Once you have this definition set, doing the integral is a matter of careful bookkeeping:

\begin{align}\int_0^1 dx \: h_n(x) = \int_0^{1/(3 \cdot 2^{n-1})} dx \: 2^n x + \sum_{m=1}^{n-1} \int_{1/(3 \cdot 2^{n-m})}^{1/(3 \cdot 2^{n-m-1})} dx \left [(2^{n-2 m} x + \left (1-\frac{1}{2^m}\right )\right ]\\ + \int_{1/3}^1 dx \: \left [\frac{1}{2^n} x +\left (1-\frac{1}{2^n}\right )\right ] \\\end{align}

I again leave the algebra to the reader; the result is

$$\int_0^1 dx \: h_n(x) = 1 – \frac{n+3}{6 \cdot 2^n}$$