Putnam 1996, Problem A-6

Let \( c > 0 \) be a constant. Give a complete description, with proof, of the set of all continuous functions \( f : R \to R \) such that \( f(x) = f(x^2 + c) \) for all \( x \in R \). Note that \( R \) denotes the set of real numbers.

Solution:
We first consider the case \(c \leq 1/4\); we shall show in this case \(f\) must be constant. The relation  
\[
f(x) = f(x^2 + c) = f((-x)^2 + c) = f(-x)
\]  
proves that \(f\) is an even function. Let \(r_1 \leq r_2\) be the roots of \(x^2 + c - x\), both of which are real. If \(x > r_2\), define \(x_0 = x\) and \(x_{n+1} = \sqrt{x_n - c}\) for each positive integer \(x\). By induction on \(n\), \(r_2 < x_{n+1} < x_n\) for all \(n\), so the sequence \(\{x_n\}\) tends to a limit \(L\) which is a root of \(x^2 + c = x\) not less than \(r_2\). Of course this means \(L = r_2\). Since \(f(x) = f(x_n)\) for all \(n\) and \(x_n \to r_2\), we conclude \(f(x) = f(r_2)\), so \(f\) is constant on \(x \geq r_2\).  

If \(r_1 < x < r_2\) and \(x_n\) is defined as before, then by induction, \(x_n < x_{n+1} < r_2\). Note that the sequence can be defined because \(r_1 > c\); the latter follows by noting that the polynomial \(x^2 - x + c\) is positive at \(x = c\) and has its minimum at \(1/2 > c\), so both roots are greater than \(c\). In any case, we deduce that \(f(x)\) is also constant on \(r_1 \leq x \leq r_2\).  

Finally, suppose \(x < r_1\). Now define \(x_0 = x, x_{n+1} = x_n^2 + c\). Given that \(x_n < r_1\), we have \(x_{n+1} > x_n\). Thus if we had \(x_n < r_1\) for all \(n\), by the same argument as in the first case we deduce \(x_n \to r_1\) and so \(f(x) = f(r_1)\). Actually, this doesn’t happen; eventually we have \(x_n > r_1\), in which case \(f(x) = f(x_n) = f(r_1)\) by what we have already shown. We conclude that \(f\) is a constant function.  

(Thanks to Marshall Buck for catching an inaccuracy in a previous version of this solution.)  

Now suppose \(c > 1/4\). Then the sequence \(x_n\) defined by \(x_0 = 0\) and \(x_{n+1} = x_n^2 + c\) is strictly increasing and has no limit point. Thus if we define \(f\) on \([x_0, x_1]\) as any continuous function with equal values on the endpoints, and extend the definition from \([x_n, x_{n+1}]\) to \([x_{n+1}, x_{n+2}]\) by the relation \(f(x) = f(x^2 + c)\), and extend the definition further to \(x < 0\) by the relation \(f(x) = f(-x)\), the resulting function has the desired property. Moreover, any function with that property clearly has this form.