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.
Solutions are also available in: Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
6 June 2002