### 49th Putnam 1988

Problem A1

R+ denotes the positive reals. Prove that there is a unique function f : R+ → R+ satisfying f( f(x) ) = 6x - f(x) for all x.

Solution

Answer: unique solution is f(x) = 2x.

Moderately hard

To get a handle on the problem, we try taking f(x) linear. Solving gives the solutions f(x) = -3x or f(x) = 2x, but the first is ruled out because the values must be positive. So we have to prove that f(x) = 2x is the only solution.

It is obviously the only polynomial solution, but we are not even given that f is continuous. In principle, it could be an entirely arbitary function. So we must somehow use the relation f( f(x) ) = 6x - f(x) directly to get a contradiction. The only obvious approach is to define a sequence xn+1 = f(xn) and hope that we eventually get xn negative. A little experimentation suggests that that is true.

So suppose we have f(x0) = (2 - λ0)x0 for some x0 with 0 < λ0 < 2. Then f( (2 - λ0)x0) = (4 + λ0)x0, and hence f( (4 + λ0)x0 ) = (8 - 7λ0)x0 = (2 - 9λ0/(4 + λ0) ) (4 + λ0)x0. In other words, we have found x1 and λ1 = 9λ0/(4 + λ0) such that f(x1) = (2 - λ1)x1. But λ1 > 3/2 λ0. If λ1 > 2, then we have a contradiction (because f(x1) < 0). If not, then we can repeat to get an x2 with f(x2) = (2 - λ2)x2 and λ2 > 3/2 λ1 > (3/2)2 λ0. And so on. So if we can find x0 with f(x0) < 2x0 then we have a contradiction.

If we can find x0 with f(x0) > 2x0, then f(x0) = (2 + λ)x0 for some λ > 0. So f( (2 + λ)x0) = (4 - λ)x0 < 2 (2 + λ)x0. In other words, we have found x1 = (2 + λ)x0 such that f(x1) < 2x1 and hence have a contradiction. So we must have f(x) = 2x for all x.