The function f is defined on the set of positive integers and its values are positive integers. Given that f(n+1) > f(f(n)) for all n, prove that f(n) = n for all n.
Solution
The first step is to show that f(1) < f(2) < f(3) < ... . We do this by induction on n. We take Sn to be the statement that f(n) is the unique smallest element of { f(n), f(n+1), f(n+2), ... }.
For m > 1, f(m) > f(s) where s = f(m-1), so f(m) is not the smallest member of the set {f(1), f(2), f(3), ... }. But the set is bounded below by zero, so it must have a smallest member. Hence the unique smallest member is f(1). So S1 is true.
Suppose Sn is true. Take m > n+1. Then m-1 > n, so by Sn, f(m-1) > f(n). But Sn also tells us that f(n) > f(n-1) > ... > f(1), so f(n) >= n - 1 + f(1) >= n. Hence f(m-1) >= n+1. So f(m-1) belongs to { n+1, n+2, n+3, .. }. But we are given that f(m) > f(f(m-1)), so f(m) is not the smallest element of { f(n+1), f(n+2), f(n+3), ... }. But there must be a smallest element, so f(n+1) must be the unique smallest member, which establishes Sn+1. So, Sn is true for all n.
So n <= m implies f(n) <= f(m). Suppose for some m, f(m) >= m+1, then f(f(m)) >= f(m+1). Contradiction. Hence f(m) <= m for all m. But since f(1) >=1 and f(m) > f(m-1) > ... > f(1), we also have f(m) >= m. Hence f(m) = m for all m.