9th Chinese 1994 Problem A3 X is the interval [1, ∞). Find all functions f: X → X which satisfy f(x) ≤ 2x + 2 and x f(x + 1) = f(x) 2 - 1 for all x.
If f(x) ≤ k(x + 1) for some k > 1 and all x, then f(x) 2 = x f(x+1) + 1 ≤ x k(x + 2) + 1 ≤ kx 2 + 2kx + k = k(x + 1) 2 , so f(x) ≤ k 1/2 (x + 1). So starting with the inequality given (k = 2), we obtain f(x) ≤ 2 1/N (x + 1), for N = 2, 4, 8, 16, ... and hence f(x) ≤ x + 1. Now suppose f(b)  0. Hence f(b+1)  3/2 k. Now (3/2) m k tends to infinity faster than m, so for m sufficiently large we must get B = b +m, with f(B) = B+1 - k with k > B/2. But then f(B)  12. So by repeated application of (*) we must eventually get c > 3 with f(c) ≤ 2. But then f(c + 1) < 3/c < 1. Contradiction. So the only solution is f(x) = x + 1. 9th Chinese 1994 © John Scholes jscholes@kalva.demon.co.uk 25 June 2002