$f\colon\mathbb{R}\to\mathbb{R}$ such that $f(x)+f(f(x))=x^2$ for all $x$?

Question

A friend came up with this problem, and we and a few others tried to solve it. It turned out to be really hard, so one of us asked his professor. I came with him, and it took me, him and the professor about an hour to say anything interesting about it.

We figured out that for positive $x$, assuming $f$ exists and is differentiable, $f$ is monotonically increasing. (Differentiating both sides gives $f'(x)*[\text{positive stuff}]=2x$). So $f$ is invertible there. We also figured out that f becomes arbitrarily large, and we guessed that it grows faster than any linear function. Plugging in $f{-1}(x)$ for $x$ gives $x+f(x)=[f^{-1}(x)]^2$. Since $f(x)$ grows faster than $x$, $f^{-1}$ grows slower and therefore $f(x)=[f^{-1}(x)]^2-x\le x^2$.

Unfortunately, that's about all we know... No one knew how to deal with the $f(f(x))$ term. We don't even know if the equation has a solution. How can you solve this problem, and how do you deal with repeated function applications in general?

Answer 1

Some observations (without assuming differentiability):

First, monotonicity in the left and right half line does not require differentiability. Observe that if there exists $x_0, y_0\in\mathbb{R}$ such that $f(x_0) = f(y_0)$, then necessarily $f(f(x_0)) = f(f(y_0))$ and hence $x_0^2 = y_0^2$. So this implies that $f$ is injective among the positive (negative) numbers. If you assume we are looking for continuous solutions, this also implies that $f$ is monotonic in the region concerned. Also, one gets that $f(x)$ cannot be bounded from above trivially because $x^2$ is not bounded from above.

Next, observe that a fixed point of $f$ can only be $f(x) = x \implies 2x = x^2$, which means that the only possible fixed points of $f$ are $0$ and $2$. Along the same lines, we get that for a continuous solution, $f(0) \geq 0$: assume the contrary, then $f(0) = y < 0$. We have by the functional equation $f(y) = -y > 0$, so by continuity there exists some $y' < 0$ such that $f(y') = 0$. But this means that $f(y') + f(f(y')) = f(0) = y'^2 > 0$, a contradiction.

Third, still assuming that $f$ is continuous, we ask whether $f$ can be bounded on either of the half lines. The answer is no, as it will necessarily contradict the functional equation. Hence $f(x)$ must be unbounded in each half line. Using that $f(x)$ must be unbounded from above, we have that there are three cases: $f(+\infty) < 0$, $f(-\infty) < 0$, or neither. (Cannot be both, because of monotonicity.)

The second case can be ruled out, as for very large negative $M$, we would get $f(M) < 0$, so $f(f(M)) < f(0)$, and contradicting the functional equation. The third case will also be ruled out if $f(0) \neq 0$. By the previous arguments $f(0)$, if non-zero, must be positive, this implies that $f(f(0)) < 0$ and so $f$ cannot be monotonically increasing on the right line.

In the first case, we get that monotonicity and unboundedness imply there exists $M > 0$ such that if $|x| > M$, $x f(x) < 0$ (in fact, using $f(0) + f(f(0)) = 0$, one can take $M= |f(0)|$). In particular this means that for $x < -M$, $f(f(x)) < f(0) < f(x) \implies f(x) \geq x^2 / 2$. But we can assume (by choosing a larger $M$ if necessary) that $M > 2$, which implies that $f(x) > M$, which implies that in fact $f(f(x)) < 0$ for $x < -M$. And hence $f(x) \geq x^2$ if $x < -M$. This implies that for sufficiently large and positive $x$, $x^2 = f(f(x))+ f(x) \geq f(x)^2 + |f(x)|$. This implies that for sufficiently large and positive $x$, $|f(x)| < x$.

In the third case, monotonicity and positivity guarantees that $f(x) < x^2$ for $x > 0$. And given a solution on the right half line, setting $f(x) = f(-x)$ on the left half line gives automatically a continuous solution. Furthermore, we can show that $f(x)$ cannot be $O(x^\alpha)$ for any $\alpha < \sqrt{2}$. (Assume the contrary, for all sufficiently large $x$ we have $f(x) + f(f(x))\leq C x^{(\alpha^2)}$ for a universal constant $C$, and so contradicts the functional equation.) Similarly $f(x)$ cannot be bounded below, asymptotically, by any $\beta x^\alpha$ with $\alpha > \sqrt{2}$.

---

BTW, I don't think your argument that "if $f$ is differentiable that $f(x)$ must be increasing for positive $x$" is correct. You used the fact that $f(x)$ is arbitrarily large (and positive) somewhere. But it doesn't have to be so for positive $x$: in that step you are making the assumption that $f:\mathbb{R}_+ \to \mathbb{R}_+$, which is not necessarily true.

Answer 2

Here is something: Iterating

$$f_0(x):=0, \quad f_{n+1}(x):= x^2-f_n\bigl(f_n(x)\bigr)$$

one obtains a sequence of polynomials whose lowest terms stabilize at

$$x^2-x^4+2x^6-4x^8+8x^{10}-16 x^{12}+32 x^{14}-65 x^{16}+\ldots-17316 x^{28} +\ldots\ .$$

The sequence of coefficients so obtained (apart from the sign) is listed here: OEIS, but I can't make anything out of the explanation given there.

Answer 3

EDIT: the first couple of times I tried to post this answer, it refused. It turns out there is a 30,000 character maximum for answers, probably for questions. So I cut the table down, previously it was $ 5 \geq x \geq -1.$

ORIGINAL: Well, this was fun. I am not sure how to do your actual problem, So, instead, I solved the easier $$ f(f(x)) = x + x^2,$$ by a little-known procedure due to J. Ecalle, about 1973. The method is described in a book by M. Kuczma, B. Chococzewski, R. Ger, called Iterative Functional Equations. I give the value of $f(x)$ for $ 3 \geq x \geq -1.$

The basic task, once each on either side of $0,$ is to find a Fatou coordinate $\alpha$ that solves $$ \alpha(h(x)) = \alpha(x) + 1,$$ where in this case we take $h(x) = x + x^2.$ Then we find the desired $f$ by taking $$ f(x) = \alpha^{-1} \left( \frac{1}{2} + \alpha(x) \right).$$ Note that it is necessary to find the inverse function of $\alpha.$ I did this by a numerical bisection, and I'm afraid that I wrote it assuming $\alpha$ was decreasing, so for this output I had to use $-\alpha$ and subtract $1/2$ instead of add it, things like that. The inverse function is the easiest part mathematically but the worst part of the program.

Anyway, if you simultaneously graph, on the same xy-axes, $(x,x + x^2)$ along with the diagonal line $(x,x)$ and the new curve $(x,f(x)),$ well, it is a nice picture. I have a website with all the relevant background, but the host computer is down for another few weeks.

Note that, by nature, this extends to a holomorphic function on a narrow open set containing the positive reals, another containing the interval $(-1,1),$ a third containing $(-\infty, -1).$ However, the function is probably only $C^\infty$ at $-1$ and $0.$

EDIT TOO: Note that the symmetry $h(-1-x) = h(x)$ carries over to the "answer" $f(x),$ so we know what we have once we know $f(x),$ or how to calculate $f(x),$ for $x \geq \frac{-1}{2}.$ On that note, we now find $ f(\frac{-1}{2}) \approx -0.308725 < \frac{-1}{4} = h(\frac{-1}{2}),$ which is how it should be, $f(x)$ should be between $x$ and $h(x).$ What we have done, successful except for not being analytic along the entire line (and not definable in neighborhoods of $0$ or $-1$ in $\mathbb C$) is produce a parametrized family of interpolating functions, $$ h_t(x) = \alpha^{-1} \left( t + \alpha(x) \right).$$ The defining properties are $$h_0(x) = x, \; \; h_1(x) = h(x), \; \; h_{s+t}(x) = h_s(h_t(x)) = h_t(h_s(x)). $$ So we simply took $f = h_{1/2}.$ The reason this particular family is considered a failure, from the viewpoint of Irvine Noel Baker (1932-2001), is precisely the failure to extend to an open set in $\mathbb C,$ caused by trouble at $-1$ and $0.$ Final note, if this business actually works out as Irvine intended, one may also throw in complex parameters $t.$ This is rare. The only example I know is the family of Moebius transformations, $$ h_t(z) = \frac{z}{1+ t z}.$$ Of course, given some holomorphic $\omega(z)$ with $\omega(0)=0$ and $\omega'(0)=1,$ one obtains a superficially different example $ H_t(z) = \omega^{-1}( h_t(\omega(z))).$

As was pointed out in a comment, there is an explicit solution to $g(g(x)) = x^2$ given by $g(x) = |x|^{\sqrt 2}.$ It is likely that our $f(x)$ is close to $|x|^{\sqrt 2}$ for large $|x|.$ It is always possible that our $f(x)$ has an explicit formula, I did not check that carefully, as I did not expect it.

In case of interest, email me. I know things.

x           alpha(x)      f(x)        f(f(x))   f(f(x)) - (x + x^2)
3.000000   -0.101309    5.447411    12.000000    -3.89775e-10
2.990000   -0.098108    5.423742    11.930100    5.07214e-09
2.980000   -0.094892    5.400101    11.860400    -1.10352e-09
2.970000   -0.091660    5.376488    11.790900    9.5132e-09
2.960000   -0.088411    5.352904    11.721600    -1.51e-08
2.950000   -0.085146    5.329349    11.652500    -1.76893e-10
2.940000   -0.081865    5.305822    11.583600    -1.56864e-09
2.930000   -0.078567    5.282324    11.514900    1.1039e-09
2.920000   -0.075252    5.258855    11.446400    -6.60402e-09
2.910000   -0.071920    5.235415    11.378100    1.83272e-08
2.900000   -0.068572    5.212003    11.310000    6.31031e-09
2.890000   -0.065206    5.188620    11.242100    -7.84935e-09
2.880000   -0.061823    5.165266    11.174400    4.82576e-09
2.870000   -0.058422    5.141941    11.106900    3.31783e-10
2.860000   -0.055004    5.118646    11.039600    2.35487e-09
2.850000   -0.051567    5.095379    10.972500    2.28822e-09
2.840000   -0.048113    5.072141    10.905600    -2.35738e-09
2.830000   -0.044641    5.048933    10.838900    1.52213e-08
2.820000   -0.041150    5.025754    10.772400    -8.93154e-09
2.810000   -0.037641    5.002604    10.706100    -4.66779e-09
2.800000   -0.034113    4.979483    10.640000    3.93858e-10
2.790000   -0.030567    4.956392    10.574100    9.60916e-09
2.780000   -0.027001    4.933330    10.508400    6.95821e-10
2.770000   -0.023416    4.910298    10.442900    -1.74676e-10
2.760000   -0.019812    4.887296    10.377600    6.04472e-09
2.750000   -0.016189    4.864323    10.312500    -6.78922e-09
2.740000   -0.012545    4.841379    10.247600    3.59014e-09
2.730000   -0.008882    4.818466    10.182900    -5.07475e-09
2.720000   -0.005198    4.795582    10.118400    5.82313e-09
2.710000   -0.001495    4.772728    10.054100    4.54672e-09
2.700000   0.002229    4.749904    9.990000    1.92885e-11
2.690000   0.005974    4.727110    9.926100    1.17165e-09
2.680000   0.009740    4.704346    9.862400    -1.02179e-09
2.670000   0.013527    4.681612    9.798900    1.49861e-09
2.660000   0.017335    4.658908    9.735600    3.89245e-10
2.650000   0.021164    4.636234    9.672500    1.00368e-08
2.640000   0.025016    4.613590    9.609600    -6.6567e-09
2.630000   0.028889    4.590977    9.546900    3.70571e-09
2.620000   0.032784    4.568394    9.484400    1.38761e-08
2.610000   0.036702    4.545842    9.422100    -4.83761e-09
2.600000   0.040642    4.523320    9.360000    9.87709e-09
2.590000   0.044605    4.500828    9.298100    9.348e-09
2.580000   0.048591    4.478368    9.236400    -2.90049e-09
2.570000   0.052600    4.455937    9.174900    -5.91812e-09
2.560000   0.056633    4.433538    9.113600    7.64032e-10
2.550000   0.060689    4.411169    9.052500    1.4757e-09
2.540000   0.064770    4.388831    8.991600    -6.12545e-10
2.530000   0.068875    4.366524    8.930900    9.22328e-09
2.520000   0.073004    4.344248    8.870400    6.82412e-09
2.510000   0.077158    4.322003    8.810100    3.96887e-10
2.500000   0.081336    4.299789    8.750000    -2.99742e-10
2.490000   0.085540    4.277606    8.690100    8.97266e-09
2.480000   0.089770    4.255454    8.630400    9.81059e-11
2.470000   0.094025    4.233334    8.570900    4.32604e-10
2.460000   0.098307    4.211245    8.511600    -3.40024e-11
2.450000   0.102614    4.189187    8.452500    -2.69127e-09
2.440000   0.106949    4.167161    8.393600    3.91647e-09
2.430000   0.111310    4.145166    8.334900    7.10094e-09
2.420000   0.115698    4.123203    8.276400    -9.34695e-09
2.410000   0.120114    4.101272    8.218100    -2.39256e-09
2.400000   0.124557    4.079372    8.160000    -2.51499e-09
2.390000   0.129029    4.057504    8.102100    -1.53317e-09
2.380000   0.133529    4.035668    8.044400    -7.4922e-11
2.370000   0.138057    4.013864    7.986900    1.24882e-09
2.360000   0.142615    3.992091    7.929600    -1.44446e-09
2.350000   0.147202    3.970351    7.872500    -1.58503e-10
2.340000   0.151818    3.948643    7.815600    -5.74248e-09
2.330000   0.156465    3.926967    7.758900    2.86983e-09
2.320000   0.161141    3.905323    7.702400    6.34277e-10
2.310000   0.165849    3.883712    7.646100    1.91794e-09
2.300000   0.170587    3.862133    7.590000    -6.59022e-09
2.290000   0.175357    3.840587    7.534100    2.98792e-09
2.280000   0.180158    3.819073    7.478400    -9.48332e-10
2.270000   0.184992    3.797591    7.422900    -3.32311e-09
2.260000   0.189858    3.776143    7.367600    -8.03366e-10
2.250000   0.194756    3.754727    7.312500    -1.0734e-09
2.240000   0.199688    3.733344    7.257600    -1.27912e-10
2.230000   0.204654    3.711993    7.202900    6.48889e-09
2.220000   0.209653    3.690676    7.148400    -3.59193e-09
2.210000   0.214687    3.669392    7.094100    -3.15102e-10
2.200000   0.219755    3.648141    7.040000    3.13407e-10
2.190000   0.224859    3.626923    6.986100    -1.07361e-09
2.180000   0.229998    3.605738    6.932400    -3.69792e-09
2.170000   0.235174    3.584587    6.878900    -7.75705e-10
2.160000   0.240386    3.563469    6.825600    4.24772e-10
2.150000   0.245634    3.542384    6.772500    -1.96853e-10
2.140000   0.250921    3.521333    6.719600    2.54623e-09
2.130000   0.256245    3.500316    6.666900    2.36294e-09
2.120000   0.261607    3.479332    6.614400    5.06827e-09
2.110000   0.267008    3.458383    6.562100    1.67262e-09
2.100000   0.272448    3.437467    6.510000    3.19921e-10
2.090000   0.277928    3.416585    6.458100    -6.2056e-11
2.080000   0.283448    3.395737    6.406400    -2.17898e-10
2.070000   0.289009    3.374923    6.354900    1.32299e-09
2.060000   0.294612    3.354143    6.303600    -4.07069e-10
2.050000   0.300256    3.333398    6.252500    6.40859e-10
2.040000   0.305942    3.312687    6.201600    2.31068e-10
2.030000   0.311672    3.292010    6.150900    -4.17103e-11
2.020000   0.317444    3.271368    6.100400    1.14831e-09
2.010000   0.323261    3.250760    6.050100    7.08263e-10
2.000000   0.329122    3.230188    6.000000    -4.5745e-09
1.990000   0.335029    3.209650    5.950100    -6.42627e-09
1.980000   0.340981    3.189146    5.900400    -3.42394e-09
1.970000   0.346980    3.168678    5.850900    -3.15673e-09
1.960000   0.353025    3.148245    5.801600    -2.28888e-09
1.950000   0.359118    3.127847    5.752500    3.42631e-10
1.940000   0.365260    3.107484    5.703600    -4.73638e-10
1.930000   0.371450    3.087156    5.654900    1.91659e-09
1.920000   0.377690    3.066864    5.606400    -1.26383e-09
1.910000   0.383981    3.046607    5.558100    -3.19826e-09
1.900000   0.390322    3.026386    5.510000    3.7766e-10
1.890000   0.396715    3.006200    5.462100    3.34769e-09
1.880000   0.403160    2.986050    5.414400    1.70795e-09
1.870000   0.409659    2.965936    5.366900    -4.34776e-10
1.860000   0.416211    2.945858    5.319600    3.49395e-10
1.850000   0.422818    2.925815    5.272500    4.95744e-10
1.840000   0.429481    2.905809    5.225600    -1.7308e-09
1.830000   0.436200    2.885839    5.178900    1.25981e-09
1.820000   0.442975    2.865906    5.132400    -1.68049e-09
1.810000   0.449809    2.846008    5.086100    4.21289e-10
1.800000   0.456702    2.826148    5.040000    -7.46454e-11
1.790000   0.463654    2.806323    4.994100    -4.28727e-11
1.780000   0.470666    2.786536    4.948400    1.04275e-10
1.770000   0.477740    2.766785    4.902900    2.13125e-09
1.760000   0.484876    2.747071    4.857600    3.24237e-10
1.750000   0.492076    2.727394    4.812500    -1.40458e-10
1.740000   0.499340    2.707754    4.767600    2.58735e-09
1.730000   0.506669    2.688152    4.722900    -1.44411e-09
1.720000   0.514064    2.668586    4.678400    1.66093e-11
1.710000   0.521526    2.649058    4.634100    1.16189e-09
1.700000   0.529057    2.629568    4.590000    6.39306e-10
1.690000   0.536657    2.610115    4.546100    1.64964e-09
1.680000   0.544327    2.590699    4.502400    6.04131e-09
1.670000   0.552069    2.571322    4.458900    -3.16091e-09
1.660000   0.559884    2.551982    4.415600    1.83026e-09
1.650000   0.567772    2.532680    4.372500    3.74477e-10
1.640000   0.575735    2.513417    4.329600    -3.6283e-09
1.630000   0.583775    2.494191    4.286900    -1.86412e-09
1.620000   0.591893    2.475004    4.244400    -5.64659e-10
1.610000   0.600089    2.455856    4.202100    1.02487e-10
1.600000   0.608365    2.436746    4.160000    2.39595e-09
1.590000   0.616722    2.417674    4.118100    1.08606e-10
1.580000   0.625163    2.398642    4.076400    -3.66385e-11
1.570000   0.633688    2.379648    4.034900    4.33176e-12
1.560000   0.642298    2.360693    3.993600    -3.39132e-10
1.550000   0.650995    2.341778    3.952500    6.08593e-10
1.540000   0.659781    2.322901    3.911600    1.73258e-09
1.530000   0.668657    2.304064    3.870900    1.83526e-09
1.520000   0.677625    2.285267    3.830400    7.67767e-10
1.510000   0.686687    2.266509    3.790100    -3.78556e-10
1.500000   0.695843    2.247791    3.750000    2.88475e-09
1.490000   0.705096    2.229112    3.710100    3.97754e-10
1.480000   0.714447    2.210474    3.670400    5.09553e-09
1.470000   0.723899    2.191876    3.630900    4.78744e-10
1.460000   0.733453    2.173318    3.591600    1.82767e-09
1.450000   0.743110    2.154800    3.552500    -1.19282e-10
1.440000   0.752874    2.136322    3.513600    2.08141e-10
1.430000   0.762746    2.117886    3.474900    2.90108e-10
1.420000   0.772727    2.099490    3.436400    1.77907e-10
1.410000   0.782820    2.081134    3.398100    -9.74806e-11
1.400000   0.793028    2.062820    3.360000    1.5857e-09
1.390000   0.803351    2.044547    3.322100    2.25511e-10
1.380000   0.813794    2.026315    3.284400    -1.82166e-09
1.370000   0.824357    2.008125    3.246900    9.02738e-11
1.360000   0.835043    1.989976    3.209600    -5.12752e-10
1.350000   0.845855    1.971869    3.172500    3.21432e-10
1.340000   0.856796    1.953803    3.135600    -3.4068e-10
1.330000   0.867867    1.935779    3.098900    -5.10983e-11
1.320000   0.879071    1.917798    3.062400    -2.29747e-09
1.310000   0.890412    1.899859    3.026100    -2.92007e-09
1.300000   0.901892    1.881962    2.990000    -8.43905e-10
1.290000   0.913513    1.864107    2.954100    6.49822e-10
1.280000   0.925280    1.846296    2.918400    -6.38912e-10
1.270000   0.937194    1.828527    2.882900    -2.0813e-10
1.260000   0.949260    1.810801    2.847600    6.72884e-10
1.250000   0.961480    1.793118    2.812500    3.85402e-10
1.240000   0.973857    1.775478    2.777600    3.137e-09
1.230000   0.986396    1.757882    2.742900    -3.80674e-10
1.220000   0.999100    1.740329    2.708400    -8.53615e-10
1.210000   1.011972    1.722820    2.674100    -6.79273e-11
1.200000   1.025016    1.705355    2.640000    -8.11715e-10
1.190000   1.038236    1.687934    2.606100    1.54211e-10
1.180000   1.051636    1.670557    2.572400    -1.25454e-09
1.170000   1.065220    1.653225    2.538900    -1.92892e-10
1.160000   1.078993    1.635937    2.505600    -4.05451e-10
1.150000   1.092959    1.618693    2.472500    -3.74701e-10
1.140000   1.107122    1.601495    2.439600    4.17211e-10
1.130000   1.121488    1.584341    2.406900    -4.08593e-10
1.120000   1.136061    1.567233    2.374400    -5.48174e-11
1.110000   1.150846    1.550170    2.342100    -8.30743e-10
1.100000   1.165849    1.533153    2.310000    1.04309e-09
1.090000   1.181074    1.516182    2.278100    -6.09943e-10
1.080000   1.196528    1.499256    2.246400    -8.16229e-11
1.070000   1.212216    1.482377    2.214900    -2.10583e-09
1.060000   1.228144    1.465543    2.183600    -3.92793e-10
1.050000   1.244319    1.448757    2.152500    5.87179e-10
1.040000   1.260746    1.432016    2.121600    3.44437e-11
1.030000   1.277433    1.415323    2.090900    2.51721e-12
1.020000   1.294387    1.398677    2.060400    3.80106e-12
1.010000   1.311614    1.382078    2.030100    -7.26729e-11
1.000000   1.329122    1.365526    2.000000    -9.71611e-10
0.990000   1.346919    1.349022    1.970100    -1.57463e-10
0.980000   1.365013    1.332566    1.940400    -3.54069e-10
0.970000   1.383412    1.316158    1.910900    -1.75323e-09
0.960000   1.402125    1.299798    1.881600    1.22291e-10
0.950000   1.421161    1.283486    1.852500    -5.39419e-11
0.940000   1.440529    1.267223    1.823600    3.87696e-12
0.930000   1.460240    1.251009    1.794900    -8.80027e-11
0.920000   1.480302    1.234844    1.766400    -6.70815e-10
0.910000   1.500727    1.218728    1.738100    9.61436e-10
0.900000   1.521526    1.202662    1.710000    4.76444e-10
0.890000   1.542710    1.186646    1.682100    1.52244e-11
0.880000   1.564292    1.170679    1.654400    -2.59356e-10
0.870000   1.586283    1.154763    1.626900    1.72139e-10
0.860000   1.608698    1.138897    1.599600    -3.55223e-11
0.850000   1.631548    1.123081    1.572500    1.7131e-10
0.840000   1.654850    1.107317    1.545600    6.71472e-11
0.830000   1.678617    1.091603    1.518900    -2.38056e-10
0.820000   1.702866    1.075942    1.492400    6.20366e-11
0.810000   1.727613    1.060331    1.466100    7.01344e-12
0.800000   1.752874    1.044773    1.440000    2.18184e-10
0.790000   1.778668    1.029266    1.414100    2.87301e-11
0.780000   1.805014    1.013812    1.388400    1.12056e-12
0.770000   1.831931    0.998411    1.362900    -4.7431e-11
0.760000   1.859441    0.983062    1.337600    1.13006e-11
0.750000   1.887564    0.967767    1.312500    2.09954e-10
0.740000   1.916324    0.952525    1.287600    1.05608e-11
0.730000   1.945745    0.937337    1.262900    7.82623e-13
0.720000   1.975853    0.922202    1.238400    -6.99597e-11
0.710000   2.006673    0.907122    1.214100    1.1627e-09
0.700000   2.038236    0.892097    1.190000    2.03233e-10
0.690000   2.070569    0.877126    1.166100    1.50976e-10
0.680000   2.103705    0.862211    1.142400    -4.11901e-11
0.670000   2.137677    0.847351    1.118900    -9.65387e-11
0.660000   2.172520    0.832546    1.095600    1.18714e-10
0.650000   2.208272    0.817798    1.072500    2.30791e-10
0.640000   2.244971    0.803106    1.049600    6.31654e-12
0.630000   2.282660    0.788471    1.026900    -2.33087e-11
0.620000   2.321384    0.773893    1.004400    1.15288e-10
0.610000   2.361189    0.759372    0.982100    3.28112e-11
0.600000   2.402125    0.744909    0.960000    -2.09156e-10
0.590000   2.444248    0.730503    0.938100    -5.86392e-11
0.580000   2.487613    0.716157    0.916400    1.50482e-11
0.570000   2.532281    0.701868    0.894900    -1.43318e-10
0.560000   2.578318    0.687639    0.873600    5.24755e-11
0.550000   2.625794    0.673469    0.852500    7.99529e-11
0.540000   2.674783    0.659359    0.831600    4.63545e-11
0.530000   2.725365    0.645310    0.810900    1.25467e-10
0.520000   2.777626    0.631320    0.790400    2.53997e-11
0.510000   2.831659    0.617392    0.770100    -3.53922e-10
0.500000   2.887564    0.603525    0.750000    8.39185e-11
0.490000   2.945448    0.589719    0.730100    -2.87918e-11
0.480000   3.005427    0.575976    0.710400    3.40802e-11
0.470000   3.067627    0.562295    0.690900    -5.68594e-11
0.460000   3.132184    0.548678    0.671600    6.73626e-11
0.450000   3.199246    0.535123    0.652500    -1.79279e-10
0.440000   3.268975    0.521633    0.633600    -2.14379e-10
0.430000   3.341546    0.508206    0.614900    6.41868e-11
0.420000   3.417150    0.494845    0.596400    1.22023e-10
0.410000   3.495997    0.481548    0.578100    -1.77731e-11
0.400000   3.578318    0.468318    0.560000    -3.04637e-11
0.390000   3.664366    0.455153    0.542100    7.79335e-11
0.380000   3.754418    0.442055    0.524400    -1.84897e-11
0.370000   3.848785    0.429024    0.506900    9.56664e-12
0.360000   3.947806    0.416061    0.489600    -5.84024e-11
0.350000   4.051861    0.403166    0.472500    4.49981e-11
0.340000   4.161374    0.390340    0.455600    -1.69485e-11
0.330000   4.276816    0.377583    0.438900    7.15468e-12
0.320000   4.398717    0.364896    0.422400    -7.73566e-12
0.310000   4.527676    0.352280    0.406100    1.11767e-11
0.300000   4.664366    0.339734    0.390000    2.25533e-11
0.290000   4.809552    0.327260    0.374100    -5.10486e-11
0.280000   4.964106    0.314858    0.358400    1.52749e-12
0.270000   5.129026    0.302529    0.342900    4.35651e-11
0.260000   5.305462    0.290273    0.327600    2.75542e-12
0.250000   5.494739    0.278092    0.312500    -3.22453e-12
0.240000   5.698404    0.265985    0.297600    -1.3801e-12
0.230000   5.918265    0.253954    0.282900    -3.14961e-11
0.220000   6.156450    0.241999    0.268400    1.49281e-11
0.210000   6.415489    0.230121    0.254100    -2.50418e-12
0.200000   6.698404    0.218321    0.240000    -7.12223e-12
0.190000   7.008848    0.206599    0.226100    4.52561e-13
0.180000   7.351265    0.194957    0.212400    -4.34899e-12
0.170000   7.731133    0.183394    0.198900    5.62339e-12
0.160000   8.155275    0.171913    0.185600    -4.49102e-12
0.150000   8.632308    0.160513    0.172500    -1.1748e-12
0.140000   9.173276    0.149196    0.159600    -1.20799e-13
0.130000   9.792575    0.137962    0.146900    -6.41388e-12
0.120000   10.509337    0.126813    0.134400    -3.86587e-13
0.110000   11.349572    0.115749    0.122100    1.4411e-12
0.100000   12.349572    0.104772    0.110000    3.51549e-13
0.090000   13.561593    0.093883    0.098100    -2.25648e-12
0.080000   15.063763    0.083081    0.086400    3.12605e-12
0.070000   16.978455    0.072370    0.074900    2.08859e-12
0.060000   19.508950    0.061749    0.063600    1.90859e-12
0.050000   23.019941    0.051220    0.052500    7.76339e-13
0.040000   28.238364    0.040785    0.041600    1.86184e-14
0.030000   36.854601    0.030443    0.030900    -5.03431e-13
0.020000   53.921892    0.020198    0.020400    9.60668e-15
0.010000   104.610137    0.010050    0.010100    -1.32458e-14
0.000000     0.000000    0.000000    0.000000       0.000000
-0.010000   -95.399864    -0.009950    -0.009900    1.75667e-15
-0.020000   -46.098113    -0.019798    -0.019600    -5.05507e-16
-0.030000   -29.842086    -0.029543    -0.029100    -3.23543e-15
-0.040000   -21.801682    -0.039183    -0.038400    6.77203e-16
-0.050000   -17.030149    -0.048717    -0.047500    -2.98178e-15
-0.060000   -13.884541    -0.058142    -0.056400    -1.53207e-18
-0.070000   -11.663224    -0.067458    -0.065100    2.51252e-15
-0.080000   -10.016611    -0.076661    -0.073600    -2.55087e-15
-0.090000   -8.751164    -0.085749    -0.081900    -9.74754e-16
-0.100000   -7.751164    -0.094721    -0.090000    -6.96998e-15
-0.110000   -6.943230    -0.103575    -0.097900    7.79732e-16
-0.120000   -6.278611    -0.112307    -0.105600    -1.32528e-14
-0.130000   -5.723678    -0.120915    -0.113100    6.70552e-16
-0.140000   -5.254493    -0.129397    -0.120400    1.41379e-14
-0.150000   -4.853567    -0.137750    -0.127500    2.00334e-14
-0.160000   -4.507828    -0.145970    -0.134400    4.14615e-15
-0.170000   -4.207319    -0.154056    -0.141100    -5.10216e-15
-0.180000   -3.944323    -0.162002    -0.147600    6.49933e-15
-0.190000   -3.712771    -0.169806    -0.153900    3.42351e-15
-0.200000   -3.507828    -0.177464    -0.160000    -7.22422e-15
-0.210000   -3.325595    -0.184972    -0.165900    2.42941e-14
-0.220000   -3.162894    -0.192326    -0.171600    1.27135e-14
-0.230000   -3.017112    -0.199520    -0.177100    7.77176e-15
-0.240000   -2.886083    -0.206552    -0.182400    -1.18473e-14
-0.250000   -2.767994    -0.213414    -0.187500    3.58047e-15
-0.260000   -2.661319    -0.220102    -0.192400    4.34533e-15
-0.270000   -2.564767    -0.226611    -0.197100    -9.56715e-15
-0.280000   -2.477235    -0.232933    -0.201600    2.57919e-14
-0.290000   -2.397782    -0.239063    -0.205900    3.84106e-15
-0.300000   -2.325595    -0.244994    -0.210000    3.11617e-14
-0.310000   -2.259973    -0.250718    -0.213900    2.24888e-14
-0.320000   -2.200309    -0.256227    -0.217600    -1.50723e-14
-0.330000   -2.146072    -0.261515    -0.221100    -5.30999e-14
-0.340000   -2.096803    -0.266571    -0.224400    1.49875e-14
-0.350000   -2.052097    -0.271388    -0.227500    3.99758e-14
-0.360000   -2.011601    -0.275957    -0.230400    -6.55662e-15
-0.370000   -1.975007    -0.280268    -0.233100    3.8815e-14
-0.380000   -1.942042    -0.284311    -0.235600    2.68768e-14
-0.390000   -1.912470    -0.288077    -0.237900    7.36668e-15
-0.400000   -1.886083    -0.291557    -0.240000    1.60095e-15
-0.410000   -1.862701    -0.294741    -0.241900    2.47415e-15
-0.420000   -1.842165    -0.297619    -0.243600    9.98633e-15
-0.430000   -1.824343    -0.300182    -0.245100    3.12429e-14
-0.440000   -1.809117    -0.302423    -0.246400    2.29496e-15
-0.450000   -1.796391    -0.304333    -0.247500    -5.80314e-15
-0.460000   -1.786084    -0.305906    -0.248400    -1.56857e-16
-0.470000   -1.778133    -0.307136    -0.249100    1.21284e-14
-0.480000   -1.772489    -0.308018    -0.249600    9.7363e-15
-0.490000   -1.769116    -0.308548    -0.249900    -2.27682e-16
-0.500000   -1.767994    -0.308725    -0.250000    -3.19744e-14
-0.510000   -1.769116    -0.308548    -0.249900    -2.37684e-16
-0.520000   -1.772489    -0.308018    -0.249600    9.71632e-15
-0.530000   -1.778133    -0.307136    -0.249100    1.20984e-14
-0.540000   -1.786084    -0.305906    -0.248400    -1.9681e-16
-0.550000   -1.796391    -0.304333    -0.247500    -5.85309e-15
-0.560000   -1.809117    -0.302423    -0.246400    2.235e-15
-0.570000   -1.824343    -0.300182    -0.245100    3.11729e-14
-0.580000   -1.842165    -0.297619    -0.243600    9.90638e-15
-0.590000   -1.862701    -0.294741    -0.241900    2.38421e-15
-0.600000   -1.886083    -0.291557    -0.240000    1.50102e-15
-0.610000   -1.912470    -0.288077    -0.237900    7.25678e-15
-0.620000   -1.942042    -0.284311    -0.235600    2.67569e-14
-0.630000   -1.975007    -0.280268    -0.233100    3.86851e-14
-0.640000   -2.011601    -0.275957    -0.230400    -6.69652e-15
-0.650000   -2.052097    -0.271388    -0.227500    3.98259e-14
-0.660000   -2.096803    -0.266571    -0.224400    1.48276e-14
-0.670000   -2.146072    -0.261515    -0.221100    -5.32698e-14
-0.680000   -2.200309    -0.256227    -0.217600    -1.52521e-14
-0.690000   -2.259973    -0.250718    -0.213900    2.2299e-14
-0.700000   -2.325595    -0.244994    -0.210000    3.09619e-14
-0.710000   -2.397782    -0.239063    -0.205900    3.63121e-15
-0.720000   -2.477235    -0.232933    -0.201600    2.55721e-14
-0.730000   -2.564767    -0.226611    -0.197100    -9.79696e-15
-0.740000   -2.661319    -0.220102    -0.192400    4.10549e-15
-0.750000   -2.767994    -0.213414    -0.187500    3.33067e-15
-0.760000   -2.886083    -0.206552    -0.182400    -1.21215e-14
-0.770000   -3.017112    -0.199520    -0.177100    7.48701e-15
-0.780000   -3.162894    -0.192326    -0.171600    1.24182e-14
-0.790000   -3.325595    -0.184972    -0.165900    2.39883e-14
-0.800000   -3.507828    -0.177464    -0.160000    -7.54063e-15
-0.810000   -3.712771    -0.169806    -0.153900    3.09654e-15
-0.820000   -3.944323    -0.162002    -0.147600    6.16185e-15
-0.830000   -4.207319    -0.154056    -0.141100    -5.45023e-15
-0.840000   -4.507828    -0.145970    -0.134400    3.78755e-15
-0.850000   -4.853567    -0.137750    -0.127500    1.96643e-14
-0.860000   -5.254493    -0.129397    -0.120400    1.37583e-14
-0.870000   -5.723678    -0.120915    -0.113100    2.8032e-16
-0.880000   -6.278611    -0.112307    -0.105600    -1.36641e-14
-0.890000   -6.943230    -0.103575    -0.097900    3.46728e-16
-0.900000   -7.751164    -0.094721    -0.090000    -7.42516e-15
-0.910000   -8.751164    -0.085749    -0.081900    -1.45272e-15
-0.920000   -10.016611    -0.076661    -0.073600    -3.05214e-15
-0.930000   -11.663224    -0.067458    -0.065100    1.9874e-15
-0.940000   -13.884541    -0.058142    -0.056400    -5.44974e-16
-0.950000   -17.030149    -0.048717    -0.047500    -3.54382e-15
-0.960000   -21.801682    -0.039183    -0.038400    9.62772e-17
-0.970000   -29.842086    -0.029543    -0.029100    3.2699e-15
-0.980000   -46.098113    -0.019798    -0.019600    5.9771e-15
-0.990000   -95.399864    -0.009950    -0.009900    1.11234e-15 
-1.000000     0.000000     0.000000     0.000000       0.000000
 x           alpha(x)       f(x)        f(f(x))      f(f(x)) - (x + x^2) 

Answer 4

I have a strategy to prove that there is such a function $f$ from $[0,2] \to [0,2]$. Intriguingly, it visually appears that this function may be unique!

Let $S$ be the square $[0,2] \times [0,2]$. Define $\sigma : S \to S$ by $\sigma: (x,y) \mapsto (\sqrt{x+y}, x)$.

Let $f$ be any strictly increasing function $[0,2] \to [0,2]$ and let $\Gamma$ be the graph of $f$.
Lemma: The function $f$ obeys the required recursion if and only if $\sigma(\Gamma) = \Gamma$.

Proof: Suppose that $f$ obeys the required recursion. We first check that $\sigma(\Gamma) \subseteq \Gamma$. Let $(x,f(x)) \in \Gamma$. Since $f$ is stricty increasing, there is some $x' \in [0,2]$ with $f(x') = x$. Then $f(x') + f(f(x'))= (x')^2$ or $x+f(x)=(x')^2$, so $x' = \sqrt{x+f(x)}$ and $f(x') = x$. We see that $\sigma(x,f(x)) = (x', f(x')) \in \Gamma$ as desired.

We now check that $\Gamma \subseteq \sigma(\Gamma)$. Again, let $(x,f(x)) \in \Gamma$. Then we similarly have $\sigma(f(x), f(f(x)) )=(x,f(x))$.

Finally, suppose that $\sigma(\Gamma) = \Gamma$ for some increasing $f$. Then, for any $x \in [0,2]$, we would have $(x,f(x)) = \sigma(y, f(y))$ for some $y$. But then $y=f(x)$ and $x = \sqrt{y+f(y)}$, or $x = \sqrt{f(x)+f(f(x))}$ as desired. $\square$

So we need to find a path $\Gamma$, which is a graph of an increasing function, and is taken to itself by $\sigma$. A clearly necessary condition is that $\Gamma \subset \sigma^k(S)$ for every $k$.

Here is a plot of $\sigma^k(S)$ for $k=0$, $1$, ..., $6$.

Each $\sigma^k(S)$ is bounded between the graphs of two piecewise smooth functions, and they even appear to by Lipshcitz with a uniform constant for $k\geq 1$. My intuition is that, in that case, there always must exist a path between them. I haven't figured out how to make this precise yet; I'm posting in case someone else knows.

The really nifty thing is that it looks like $\bigcap_k \sigma^k(S)$ might itself be a path! In which case $f$ is unique! I 'm putting up this image now, to try to excite people into proving this.

Answer 5

A non-negative solution for $x \geq 0$ extends to all $x$ using $f(|x|)$. Below I will consider only solutions of this type.

A non-negative continuous solution on $[0,+\infty)$ is injective and unbounded for positive $x$, and therefore increasing, with $f(\infty)=\infty$ a fixed point for $f$.

Define an operator $G$ on functions by $G(f)=f(x)+f(f(x))$.

$f_0(x)=x^{\sqrt{2}}$ almost satisfies the equation, for large $x$, with $G(f_0) = x^2 + x^{\sqrt{2}} = x^2 + o(x^2)$.

A correction $f_1(x) = x^\sqrt{2} - px^q$ can be found, with constants $p$ and $q$ chosen uniquely to cancel the $x^\sqrt{2}$ term so that $G(f_1)=x^2 + O(x^a)$ with $a < \sqrt{2}$, for large $x$. The process can be repeated to get an asymptotic series with exponents in $\Bbb{Q}(\sqrt{2})$. It is a reasonable guess that these are the asymptotics for large $x$, but proving the simplest case, that $\lim f(x)x^{-\sqrt{2}}=1$, or that there exists at least one solution with that behavior, is a challenging problem. The simpler functional equation $F(F(x))=x^2$ has smooth solutions not asymptotic to $x^\sqrt{2}$.

If there are other fixed points of $f(x)$ they occur at $0$ or $2$.

The series solution with fixed point at $x=0$ is $f(x)=x^2 - x^4 + 2x^6 - 4x^8 + 8x^{10} - 16x^{12} + 32x^{14} - \dots$ but unfortunately the next coefficients are $65, -138, 316$ and OEIS has it listed ( http://oeis.org/A141366 ) with data suggesting that the series does not increase very fast and might have nonzero radius of convergence (less than 1/(2.9)). The ratio of adjacent coefficients increases from 2 to almost 3 over the first several hundred terms so of course it could also increase without bound.

The formal power series solution with fixed point $x=2$ has irrational coefficients. It begins $f(2+t) = 2 + at + O(t^2)$ where $a= \frac{\sqrt{17}-1}{2}$ and the higher degree coefficients are in $\Bbb{Q}(a)$.

Answer 6

UPDATE: This answer now makes significantly weaker claims than it used to.

Define the sequence of functions $f_n$ recursively by $$f_1(t)=t,\ f_2(t) = 3.8 + 1.75(t-3),\ f_k(t) = f_{k-2}(t)^2 - f_{k-1}(t)$$ The definition of $f_2$ is rigged so that $f_2(3) = 3.8$ and $f_2(3.8) = 3^2- 3.8 = 5.2$.

Set $g_k=f_k(3)=f_{k-1}(3.8)$. So the first few $g$'s are $3$, $3.8$, $5.2$, $9.24$, etc. Numerical data suggests that the $g$'s are increasing (checked for $k$ up to $40$). More specifically, it appears that $$g_n \approx e^{c 2^{n/2}} \quad \mbox{for}\ n \ \mbox {odd, where}\ c \approx 0.7397$$ $$g_n \approx e^{d 2^{n/2}} \quad \mbox{for}\ n \ \mbox {even, where}\ d \approx 0.6851$$

We have constructed the $f$'s so that $f_k(3)=g_k$ and $f_k(3.8) = g_{k+1}$. Numerical data suggests also that $f_k$ is increasing on $[3,3.8]$ (checked for $k$ up to $20$). Assuming this is so, define $$f(x) = f_{k+1} (f_{k}^{-1}(x)) \ \mathrm{where}\ x \in [g_k, g_{k+1}].$$
Note that we need the above numerical patterns to continue for this definition to make sense. This gives a function with the desired properties on $[3,\infty)$.

Moreover, we can extend the definition downwards to $[2, \infty)$ by running the recursion backwards; setting $f_{-k}(t) = \sqrt{f_{-k+1}(t) + f_{-k+2}(t)}$. Note that, if $f_{-k+1}$ and $f_{-k+2}$ are increasing then this equation makes it clear that $f_{-k}$ is increasing. Also, if $g_{-k+1} < g_{-k+2}$ and $g_{-k+2} < g_{-k+3}$ then $g_{-k} = \sqrt{g_{-k+1} + g_{-k+2}} < \sqrt{g_{-k+2} + g_{-k+3}} = g_{-k+1}$, so the $g$'s remain monotone for $k$ negative. So this definition will extend our function successfully to the union of all the $[g_k, g_{k+1}]$'s, for $k$ negative and positive. This union is $[2, \infty)$.

There is nothing magic about the number $3.8$; numerical experimentation suggests that $g_1$ must be chosen in something like the interval $(3.6, 3.9)$ in order for the hypothesis to hold.

---

I tried to make a similar argument to construct $f:[0,2] \to [0,2]$, finding some $u$ such that the recursively defined sequence $1$, $u$, $1^2-u$, $u^2-(1^2-u)$ etcetera would be decreasing. This rapidly exceeded my computational ability. I can say that, if there is such a $u$, then

$$0.66316953423239333 < u < 0.66316953423239335.$$

If you want to play with this, I would be delighted to hear of any results, but let me warn you to be very careful about round off errors!