### Putnam 1996

Problem A6

Let R be the reals and k a non-negative real. Find all continuous functions f : R → R such that f(x) = f(x2 + k) for all x.

Solution

Apart from one trap, this is straightforward.

We note that first that f(-x) = f(x), so it is sufficient to define f for non-negative x.

We note that (x2 + k) ≥ k for all x, with equality iff x = 0, so it is tempting to say that on [0, k] f is arbitary except that it must be continuous and f(0) = f(k). We then extend f to the rest of the real line using the relation given.

The trap is that this does not work for k ≤ 1/4. The extension process just generates smaller and smaller intervals which converge on a root of the equation x2 + k = x. If we try starting with a larger interval above the roots, then we can extend the function towards infinity without difficulty, but extending back to smaller values gives the same problem as before.

In fact, it is not too difficult to see that for k ≤ 1/4 the function must be constant.

Actually, spelling this out in detail is fairly painful! It is most easily seen from the graph. Let a1 < a2 be the two roots of x2 - x + k = 0. If we define x1 = a, xn+1 = xn2 + k for 0 < a < a2 (and also a ≠ a1) then xn tends to a1. By the continuity of f, f(xn) must tend to f(a1), but f is constant on the sequence, so f(a) = f(a1). Similarly, for any a > a2, we define x1 = a, xn+1 = √(xn - k). This time xn tends to a2 and by the same argument as before we must have f(a) = f(a2). But we have f(x) = f(a1) for values of x arbitarily close to a2 (and below it) and f(x) = f(a2) for values of x arbitarily close to a2 and above it, so f(a1) = f(a2) and hence f is constant.

If we want a more rigorous treatment of the fact that xn tends to the root, there is further pain! Write xn = a1 + kn, xn+1 = a1 + kn+1, then kn+1 = 2a1kn + kn2. But 0 < 2a1 < 1, so for kn < 0, we have 0 > kn+1 > 2a1kn, and hence kntends to zero. For kn > 0, we observe first that xn+1 < xn, so we have kn < k1 = a2 - a1 - ε for some ε > 0, so kn+1 = (2a1 + kn)kn < (2a1 + k1)kn = (2a1 + a2 - a1 - ε)kn = (1 - ε)kn. Hence kn tends to zero. A similar argument deals with the case a > a2. We have skated over the case k = 1/4, but I leave that as an exercise. [f is still constant. In graphical terms the curves y = x2 + 1/4 and y = √(x - 1/4) touches the line y = x at x = 1/2 and it is clear from the graph that the same sequences work as before.]