Selection tests for the International Mathematical Olympiad, 2013

Since $f$ is strictly increasing, we have $f(n) \geq n$ for all $n$ in $S$.

Assume that there exists an integer $n$ in $S$ such that $f(n) > n$. Let $n_0$ be the smallest such $n$ and write $f(n_0) = n_0 + k_0$, for some positive integer $k_0 \geq 1$. Again, since $f$ is strictly increasing, we have $f(n) \geq n + k_0$, for all integers $n \geq n_0$.

Because $k_0 \geq 1$, we have
$$f(n_0 + k_0) \geq n_0 + 2k_0.$$
On the other hand, we have
$$f(n_0 + k_0) = f(f(n_0)) \leq 2 f(n_0) - n_0 = n_0 + 2k_0$$
We deduce that
$$f(n_0 + k_0) = n_0 + 2k_0$$
Because $f(n_0) = n_0 + k_0$, $f(n_0 + k_0) = (n_0 + k_0) + k_0$ and $f$ is strictly increasing, we deduce that $f(n) = n + k_0$, for all $n_0 \leq n \leq n_0 + k_0$.

We prove by induction on $m$ that for all integer $n$ such that
$$n_0 + m k_0 \leq n \leq n_0 + (m+1) k_0$$
we have $f(n) = n + k_0$. Hence
$$f(n) = \begin{cases} n + k_0 & \text{ if } n \geq n_0 \\ n & \text{ otherwise } \end{cases}$$
Conversely, if $f$ is such a function and $n \geq n_0$ then
$$n + f(f(n)) = n + f(n + k_0) = 2n + 2k_0 = 2 f(n)$$
And if $f(n) = n$, the inequality is clearly satisfied.

Therefore, the solutions to this functional inequality are the functions that can be written as
$$f(n) = \begin{cases} n + k_0 & \text{ if } n \geq n_0 \\ n & \text{ otherwise } \end{cases}$$
for some $n_0 \in S$ and some nonnegative integer $k_0 \geq 0$.