Singapore Mathematical Olympiad (SMO)

We shall show that $f(k) = k$ for all $k$. It suffices to show that $f$ is a strictly increasing function for if $f$ is a strictly increasing function, then for an arbitrary $k$,
$$f(k+1) > f(f(k)) \Rightarrow k+1 > f(k) \Rightarrow f(k) = k.$$
Consider the set of integers $\{f(1), f(2), \dots\}$. By the given condition, each member $f(k+1), k \ge 1$ is bigger than another member $f(f(k))$, with $f(1)$ as the only exception. Therefore $f(1)$ is the smallest element of the set.
This argument can be extended. Let $g(k) = f(k) - 1$, for $k \ge 2$. Then $\{g(2), g(3), \dots\}$ is a set of positive integers. For $k \ge 2$, $g(k+1) = f(k+1) - 1 > f(f(k)) - 1 = g(f(k)) = g(g(k) + 1)$. This means $g(2)$ is the smallest element of the set. Therefore $f(1) < f(2) < f(k)$ for all $k \ge 3$. Continuing this way, we see that $f(1) < f(2) < f(3) < \dots$, i.e., the function $f$ is strictly increasing.