Is there a function such that $f(f(n)) = 2^n$?

Solution 1:

I'm having trouble getting the 2; Helmut Kneser showed that there is a real analytic function, call it $h(x),$ such that $$ h(h(x)) = e^x. $$

It might be necessary to redo the whole argument to get $2.$ Kneser and related papers at MEEEEEEEEEEEEEEEEEEEEE

A good example is the half iterate of $\sin x,$ it took me quite a while, but see https://mathoverflow.net/questions/45608/formal-power-series-convergence/46765#46765

on average, a decreasing function rules out any half iterate, $\sin x$ is an extremely special case.

Note that if we just ask for differentiabilty, there is a theorem in the KCG book that gives it. I think I included that in the excerpts on my website.

Solution 2:

It is possible to define such function piecewise, too. Assume that $f(0)=\frac{1}{2}$, then $f(1/2)=1$.

Let $I_0=[0,1/2]$ and define $f$ over $I_0$ as $$f(x)=x+\frac{1}{2}.$$ Since $f(1)=\sqrt{2}$, we can take $I_1=[1/2,1]$ and define $f$ over $I_1$ as $$f(x)=2^{x-1/2},$$ then $f$ over $I_2=[1,\sqrt{2}]$ as $$f(x)=x\sqrt2,$$ $f$ over $I_3=[\sqrt{2},2]$ as $$f(x)=2^{x/\sqrt2},$$ $f$ over $I_4=[2,2^\sqrt2]$ as $$f(x)=x^\sqrt{2},$$ $f$ over $I_5=[2^\sqrt2,4]$ as $$f(x)=2^{x^{1/\sqrt2}},$$ $f$ over $I_6=[4,2^{2^\sqrt2}]$ as $$f(x)=2^{(\log_2 x)^{\sqrt2}},$$ $f$ over $I_7=[2^{2^\sqrt 2},16]$ as $$f(x)=2^{2^{(\log_2 x)^{1/\sqrt2}}},$$ $f$ over $I_8=[16,2^{2^{2^\sqrt2}}]$ as $$f(x)=2^{2^{(\log_2 \log_2 x)^{\sqrt2}}}$$ and so on.

We have $I_{n+1}=[\max I_n,2^{\min I_n}]$ and given that $g_n$ is the inverse function of $f_{|I_n}$, $$f_{|I_{n+1}}=2^{g_n}.$$ Continuity and monotonicity are met.