### 62nd Putnam 2001

Problem B5

f is a continuous real-valued function on the reals such that for some 0 < a, b < 1/2, we have f(f(x)) = a f(x) + b x for all x. Show that for some constant k, f(x) = k x for all x.

Solution

Notice first that if f(x) = kx, then f(f(x)) = k2x, so k2x = akx + bx and hence k is a root of the quadratic t2 - at - b = 0.

If f(x) = f(y), then f(f(x)) = f(f(y)), so x = ( f(f(x)) - a f(x) )/b = ( f(f(y)) - a f(y) )/b = y. In other words, f is one-to-one. Since it is continuous, it must be strictly increasing or strictly decreasing. It cannot be bounded as x tends to plus infinity, otherwise f(f(x)) would be bounded, but a f(x) + b x would be unbounded. Similarly as x tends to minus infinity. So f must be onto and hence invertible.

Let h, k be the roots of t2 = a t + b. Evidently one root, say h, is positive and the other negative. Moreover both must have absolute value less than 1. This is where we need 0 < a, b < 1/2. Write h = (a + √(a2 + 4b) )/2, k = (a - √(a2 + 4b) )/2, and it follows immediately that 0 < h < 1, 0 > k > -h.

Now given x, take p, q so that x = p + q, f(x) = ph + qk. It is easy to see that this can be done: p = (f(x) - kx)/(h - k), q = (hx - f(x) )/(h - k). It is also easy to see that denoting f2(x) = f(f(x)), f3(x) = f(f2(x)) etc, we have fn(x) = phn + qkn. Indeed this must also be true for n negative, where f-1 denotes the inverse of f.

Now suppose f is increasing. Suppose for some particular x we have q non-zero. Then for n sufficiently large, qk-n dominates ph-n, so f -n(x) alternate in sign but increases in absolute value as n increases. For suitable N we will have f -N-2(x) > f -N(x) > 0, but f -N-1(x) < f -N+1(x) < 0. In other words A > B, but f(A) < f(B), contradicting the fact that f is increasing. So we must have q zero for all x. Hence f(x) = hx for all x.

Similarly, suppose f is decreasing. Suppose for some particular x we have p non-zero. Then for sufficiently large n, phn dominates qkn, so f n(x) has the same sign, but decreases in absolute value as n increases. So either we have N with f N-1(x) > f N(x) > f N+1(x) > f N+2(x) > 0, in which case A > B but f(A) > f(B) (with A = f N-1(x), B = f N+1(x) ), or we have N with f N-1(x) < f N(x) < f N+1(x) < f N+2(x) < 0, in which case A < B but f(A) < f(B) (with A = f N-1(x), B = f N+1(x) ). In either case we contradict f decreasing. So if f is decreasing we must have p zero for all x and hence f(x) = kx for all x.