Many years ago, I worked on the following problem. Given a real analytic function $F(x)$, find a continuously differentiable real function $f(x)$ such that $\forall{x}. F(x) = f(f(x))$. I was able to derive an infinite series for $f(x)$ provided that 1) $F(x)$ had a fixed point, i.e. a value $\lambda$ such that $F(\lambda)=\lambda$, and some other restriction 2) that I have forgotten, but might have been that $F(x)$ was monotone increasing.
It was a pleasant surprise to see this question asking for solutions to a very similar question.
Anyway, about 35 years ago, I gave my solution to a mathematician, and suggested that he publish it. I don't recall his name, but I assume it was never published. I have forgotten all the details, but I can relay as much of what I remember, and if anyone can solve this before I am able to recreate the solution, they can have credit for the solution.
One thing to note with respect to a solution $f(x)$ such that $F(x)=f(f(x))$. If $\lambda$ is a fixed point of $F(x)$, that is $F(\lambda)=\lambda$, then $f(\lambda)$ is also a fixed point of $F(x)$. That is $F(f(\lambda)) = f(\lambda)$. So, if $F(x)$ has only one fixed point, i.e. $\lambda$, then $\lambda$ is also a fixed point of $f(x)$, and it is the unique such fixed point.
One of the steps in finding the solution was to shift the function $F(x)$ along the line $y=x$, so that some fixed point $\lambda$ was moved to the origin. That is, we define a transformed function $F^*(x) = F(x+\lambda)-\lambda$. We note that if $f^*(x) = f(x+\lambda)-\lambda$, then $F^*(x) = f^*(f^*(x))$. Also note that $F^*(0) = 0$. Thus, for a given $F(x)$, we find the solution $f^*(x)$ for $F^*(x)$, then find $f(x)$ from $f^*(x)$. Without loss of generality, we only solve problems with a fixed point at $0$.
Another step is to notice the pattern when taking the $n^{th}$ derivative of a function $f(f(x))$. That is,
$$F'(x) = (f(f(x)))' = f'(f(x))f'(x)$$ $$F''(x) (f(f(x)))'' = (f'(f(x))f'(x))' = f''(f(x))f'(x)^2 + f'(f(x))f''(x)$$ $$etc.$$
Each term in the expansion of the $n^{th}$ derivative of $f(f(x))$ is of the form
$$C_{(\beta_1, \beta_2, ...\beta_k)} f^{(k)}(f(x))\cdot\prod_{i=1}^k (f^{(i)}(x))^{\beta_i}$$
where the sum of all the exponents $\beta_i$ in the $\Pi$ term is $k$,
$$k = \sum_{i=1}^k \beta_i$$
and the sum of all the products $i\beta_i$ in the $\Pi$ term is $n$.
$$n = \sum_{i=1}^k i\beta_i$$
I don't recall how the coefficients of these terms is calculated, but it was related to the problem of finding the number of ways to express a whole number as the sum of m whole numbers. I remember deriving a recursive relationship for these coefficients, and later on, when the internet came into being, finding a similar sequence in a list of sequences. I'm sure someone recognizes that sequence as well.
An ansatz that I made regarding the solution is that I could choose one of the fixed points of $F(x)$ as a fixed point of $f(x)$. That is, assuming, $F(0)=0$, I would look for an $f(x)$ such that $f(0)=0$.
With that ansatz, the $n^{th}$ derivative of $f(f(x))$ at the fixed point $x=0$ becomes something like
$$F'(0) = (f(f(x)))'|_{x=0} = (f'(0))^2$$ $$F''(0) = (f(f(x)))''|_{x=0} = f''(0)(f'(0))^2 + f'(0)f''(0)$$ $$etc.$$
This suggests an algorithm for finding a series that might converge to an $f(x)$:
using the value for $F'(0)$, use the first equation above to calculate a value for $f'(0)$
using the value of $F^{(n)}(0)$ and the values of $f'(0),...f^{(n-1)}(0)$, and the $n^{th}$ equation above, calculate a value for $f^{(n)}(0)$.
create a Taylor's series that might converge to a solution for $f(x)$
However, in the solution I came up with, I didn't use that algorithm because each term in the series is calculated with a different equation. Instead I came up with a an infinite series where there was a uniform expression for the $n^{th}$ term.
I did this by finding another way to express $f(f(x))$, or if I am remembering correctly, expressing truncated versions of $f$ composed with itself.
Letting $f_n(x)$ be the polynomial
$$\sum_{i=0}^n a_i x^i$$
consisting of the first $n+1$ terms of the Taylor's expansion of $f(x)$.
What I did was compute the first $n+1$ terms of $f_n(f_n(x))$. If I recall correctly, I came up with something that looked like my expansion of the nth derivative of $f(f(x))$, just calculated in a different way. It looked so much like it, that for a long time I thought I had just derived the same formula a different way. Until one day, I noticed that they were slightly different. I was able to take the difference between two series, and that gave me a new way to calculate the terms in a series that might converge to $f(x)$.
Note that the final series that I got was not a Taylor series. Instead of $x^n$ terms, it had "weird" terms. Perhaps they were something like $x^{\sqrt n}$, or $n^x$. I don't recall at the moment, but they were definitely not a Taylor series.
That is about all the background information I can recall at the moment. I will give my own answer, if/when I can reconstruct it, unless someone answers this question first.
My question:
Given a real analytic function $F(x)$, find a continuously differentiable real function $f(x)$ (in the form of an infinite series) such that $\forall{x}.F(x)=f(f(x))$. You may impose the restrictions that $F(x)$ has a fixed point, i.e. a value $\lambda$ such that $F(\lambda)=\lambda$ and that $F(x)$ is monotone increasing.