Let $f:\mathbb{R} \to \mathbb{R}$ continuous with $f(f(x))=e^x$, show that $\lim_{x\to \infty } \frac{f(x)}{x^n}=\infty$ (Brazilian Olympiad)

Solution 1:

We'll start with a weak estimate, and then use the functional equation to improve it iteratively.

Claim: There is a constant $d > 0$ such that $ f(x) \ge x+d$ for all $x \ge 0$.

Once we have that estimate (see below for the proof), we can can continue as follows: Setting $C = e^d > 1$ we get $$ f(x) = f(e^{\ln x}) = e^{f(\ln x)} \ge e^{\ln x + d} = xe^d = Cx $$ for $x \ge 1$, then $$ f(x) = e^{f(\ln x)} \ge e^{C\ln x} = x^C $$ for $x \ge e$, and finally $$ f(x) = e^{f(\ln x)} \ge e^{(\ln x)^C} $$ for $x \ge e^e$.

It follows that $$ \frac{f(e^x)}{e^{nx}} \ge \frac{e^{x^C}}{e^{nx}} = e^{x^C-nx} \ge x^C-nx+1 $$ and therefore $$ \lim_{y \to \infty} \frac{f(y)}{y^n} = \lim_{x \to \infty} \frac{f(e^x)}{e^{nx}} = +\infty \, . $$

Proof of the claim: $f(0) > 0$ and $f$ has no fixed points (see for example thoughts about $f(f(x))=e^x$), therefore $f(x) > x$ for all $x \in \Bbb R$. Then $$ d = \min \{ f(x) - x \mid 0 \le x \le 1 \} $$ is strictly positive. Define the sequence $(E_k)$ recursively by $E_0 = 0$, $E_{k+1} = e^{E_k}$: $$ 0, 1, e, e^e, e^{e^e},\ldots $$ $f(x) \ge x+d$ holds for $E_0 \le x \le E_1$, and if it holds for $E_k \le x \le E_{k+1}$ then $$ f(x) = e^{f(\ln x)} \ge e^{\ln x + d} = xe^d \\ \ge x(1+d) = x + xd \ge x+d $$ for $E_{k+1} \le x \le E_{k+2}$. This concludes the proof of the claim, since $E_k \to \infty$.

Solution 2:

remark
It is not enough to assume (for example) that $f(f(x)) = e^x$ for all $x>1$. You must assume (as the OP says) $f(f(x))=e^x$ for all $x$. This is used in Edit 2.

The following function $f : \mathbb R \to \mathbb R$ is continuous and $f(f(x)) = e^x$ for all $x > 1$ but fails the required conclusion.

$$ f(x) = \begin{cases} -2x,\quad &x\ge T \\ e^{-x/2},\quad &x < T \end{cases} $$ Here $T \approx -0.7148$ is one of the points where the two graphs $-2x,e^{-x/2}$ cross.