If $f, g : \mathbb N \to\mathbb N$ are strictly increasing, $\exists n\in\mathbb N : f(g(g (n))) > g(f(n))$. Let $f,g : \mathbb N\to\mathbb N$ be strictly increasing functions. Prove that there exists an $n\in\mathbb N$ such that $$f(g(g(n))) > g(f(n)).$$
Someone care to elaborate a proposal?

Assume the contrary holds. Then $f(g(g(n)))\le g(f(n))$ for all $n$. In particular, $g(g(n))\le g(f(n))$, implying that $g(n)\le f(n)$ for all $n$. Hence, also $g^3(n)\le f(g^2(n))\le g(f(n))$, implying that $g^2(n)\le f(n)$ for all $n$. Proceeding this way, we can show that $g^k(n)\le f(n)$ for all $k$ and all $n$, which is clearly impossible (even for a fixed $n$).
