How to obtain $f(x)$, if it is known that $f(f(x))=x^2+x$?
There is no such $f:\mathbb C\to\mathbb C$. See this paper:
When is $f(f(z)) = az^2 + bz + c$ ?
by R. E. Rice, B. Schweizer and A. Sklar
The American Mathematical Monthly, vol. 87, no. 4 (Apr., 1980), pp. 252–263
More generally, they prove that a quadratic polynomial has no iterative roots of any order.
EDDIITT: pretty good approximation ( for $x>4,$ say) with $$ \color{blue}{ h(x) \approx x^{\sqrt 2} + \frac{x^{ \left(\sqrt 2 - 1 \right)}}{\sqrt 2} + (1 - \sqrt 2 ) }$$ The following things are true: as long as you just want $C^1$ with no hope of extending to the complex numbers, you can do it, this is a theorem in the KCG book, I put some pages as a pdf HERE . I have been curious on one technical point for four years now, smoothness of the real restriction of Ecalle's solution at the fixpoint itself, and just wrote to Prof. Ger, maybe he will write back.
Meanwhile, see https://mathoverflow.net/questions/45608/formal-power-series-convergence and the correct answer at https://mathoverflow.net/questions/45608/formal-power-series-convergence/46765#46765
Your function $x^2 + x$ also has derivative $1$ at the fixpoint $0,$ but is not a Mobius transformation. What this means is that there is a solution for $x \geq 0$ that is real analytic for $x > 0$ and can therefore be extended to a holomorphic function in an open set containing the strictly positive real axis. The technique for doing all this is due to Jean Ecalle at Orsay, about 1973. The specific steps are in the KCG book, especially pages 346-347 and 351-352. All steps are done with formal power series, abbreviated FPS in the book.
Anyway, goes like this: define $$ \color{green}{f(x) = \frac{\sqrt{1 + 4 x} - 1}{2} = \frac{2x}{1 + \sqrt{1 + 4 x}} } $$ for $x > -1/4.$ We need to use use rather than the original $x^2 + x$ because we need convergence in the iteration steps.
$$ \color{magenta}{f = x - x^2 + 2 x^3 - 5 x^4 + 14 x^5 - 42 x^6 + 132 x^7 - 429 x^8 + 1430 x^9 - 4862 x^{10} + 16796 x^{11} - 58786 x^{12} + 208012 x^{13} - 742900 x^{14} + 2674440 x^{15} + O(x^{16})} $$
$$ $$
$$ \color{magenta}{ \frac{d f}{dx} = 1 - 2 x + 6 x^2 - 20 x^3 + 70 x^4 - 252 x^5 + 924 x^6 - 3432 x^7 + 12870 x^8 - 48620 x^9 + 184756 x^{10} - 705432 x^{11} + 2704156 x^{12} - 10400600 x^{13} + 40116600 x^{14} - 155117520 x^{15} + O(x^{16}) }$$
Find several terms in the formal power series for $\lambda(x)$ that solves $$ \lambda(f(x)) = f'(x) \lambda(x), $$ or $$ \lambda \left( \frac{\sqrt{1 + 4 x} - 1}{2} \right) = \frac{\lambda(x)}{ \sqrt{1 + 4 x}}, $$ where the power series for $\lambda(x)$ is required to begin with the first term in the power series of $f(x)$ after the initial $x.$ To emphasize, you find the FPS's as above and perform this step with those FPS; I gradually extend the series for $\lambda,$ one coefficient at a time. $$ \color{magenta}{\lambda = - x^2 + x^3 - \frac{3 x^4}{2} + \frac{8 x^5}{3} - \frac{31 x^6}{6} + \frac{157 x^7}{15} - \frac{649 x^8}{30} + \frac{9427 x^9}{210} - \frac{19423 x^{10}}{210} + \frac{6576 x^{11}}{35} - \frac{2627 x^{12}}{7} + \frac{853627 x^{13}}{1155} - \frac{ 2007055 x^{14}}{ 1386} + \frac{3682190 x^{15}}{ 1287} + O(x^{16}))}$$
Next, write several terms for the reciprocal of the series, and use those in $$ \frac{1}{\lambda(x)} = \frac{d \alpha(x)}{dx},$$
$$\color{magenta}{ \frac{d \alpha}{dx} = \frac{-1}{x^2} - \frac{1}{x} + \frac{1}{2} - \frac{2x}{3} + \frac{13x^2}{12} - \frac{113x^3}{60}+ \frac{1187x^4}{360} - \frac{1754x^5}{315} + \frac{14569x^6}{1680} - \frac{176017x^7}{15120} + \frac{ 1745717x^8}{151200} - \frac{ 176434x^9}{51975} - \frac{ 147635381x^{10}}{9979200} + \frac{ 3238110769x^{11}}{129729600} + O(x^{12})}$$
Now, formally integrate to find a short series for $\alpha(x)$ that usually includes a single logarithms term and begins with a few negative powers of $x,$ so it is a logarithm term plus a Laurent expansion. This function $\alpha(x)$ satisfies $$ \alpha(f(x)) = \alpha(x) + 1. $$
$$ \color{magenta}{ \alpha = \frac{1}{x} - \log x + \frac{x}{2} - \frac{x^2}{3} + \frac{13 x^3}{36} - \frac{113 x^4}{240} + \frac{1187x^5}{1800} - \frac{877x^6}{945} + \frac{14569x^7}{11760} - \frac{176017x^8}{120960} + \frac{1745717x^9}{1360800} - \frac{88217x^{10}}{259875} + O(x^{11})}$$
To actually calculate $\alpha(x)$ for some real number $x > 0,$ define $$x_0 = x, x_1 = f(x), \; x_2 = f(x_1), \; \ldots \; x_{n+1} = f(x_n). $$ From the dfining equation for $\alpha,$ we know that $$ \alpha(x_n) - n = \alpha(x). $$ Which is very good, because $x_n$ slowly approaches $0,$ and we can find $\alpha(x)$ to arbitrary accuracy with $$ \color{magenta}{ \alpha(x) = \lim_{n \rightarrow \infty} \alpha(x_n) - n}, $$ where we are using our peculiar Laurent expansion plus logarithm term in the right hand side. We need a second numerical step, which is to have available $\alpha^{-1}(x).$ I did that with ordinary bisection, slow but reliable.
Finally, you were really interested in $$ f^{-1}(x) = x^2 + x. $$ By simple substitution, we have $$ \alpha(f^{-1}(x)) = \alpha(x) - 1. $$
Define $$\color{blue}{ h(x) = \alpha^{-1}\left( \alpha(x) - \frac{1}{2} \right)}, $$ so that $$ \alpha(h(x)) = \alpha(x) - \frac{1}{2}. $$ Then $$ h(h(x)) = \alpha^{-1}\left( \alpha(h(x)) - \frac{1}{2} \right), $$ $$ h(h(x)) = \alpha^{-1}\left( \left( \alpha(x) - \frac{1}{2} \right) - \frac{1}{2} \right) = \alpha^{-1}\left( \alpha(x) - 1 \right) = \alpha^{-1}\left( \alpha(f^{-1}(x)) \right), $$ $$ \color{blue}{ h(h(x)) = f^{-1}(x) = x^2 + x}. $$
This really is the right way to do this. It is just lots of work.
Alright, used gp-pari, the combined Laurent series with log is
If it seems convenient one may include a constant term, in the end it changes nothing.
EDIT, Friday August 29. Quicker than I expected, largely because I still had the C++ program for the sine problem and just had a few changes, all the extra tinkering was in numerical stuff, accuracy demands and so on. The half iterate is called $h(x),$ next column $h(h(x))$ which came out very well, error $h(h(x)) - x - x^2$ in final column.
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus ./abel_quadratic
x alpha(x) h(x) h(h(x)) h(h(x)) - x - x^2
0.1 12.34957156437698 0.1047722467597998 0.109999999999924 -7.601475008391654e-14
0.2 6.698404497655632 0.2183212373574808 0.2400000000057361 5.736109365137498e-12
0.3 4.664365697383913 0.3397339639152821 0.3899999999984503 -1.54972923057696e-12
0.4 3.578318349027508 0.4683176837006184 0.5599999999998941 -1.059019544150455e-13
0.5 2.887563844089283 0.6035247351861248 0.7500000000027918 2.791766817722419e-12
0.6 2.402125463031833 0.7449086888908782 0.9600000000071434 7.143410320729904e-12
0.7 2.038235616342387 0.8920969377271455 1.189999999998397 -1.603108759021948e-12
0.8 1.752874096376789 1.044772606289452 1.43999999999838 -1.619762104391326e-12
0.9 1.521526085243185 1.202662081576193 1.710000000007093 7.093339262319309e-12
1 1.329122322128679 1.365526109628094 1.999999999995433 -4.567457523307894e-12
1.1 1.16584868546157 1.533153249918291 2.309999999999778 -2.227196291976208e-13
1.2 1.025015540899213 1.70535494330933 2.640000000005576 5.575815417019347e-12
1.3 0.9018917080819405 1.881961717365725 2.990000000005553 5.552944822712069e-12
1.4 0.7930276007682336 2.06282021339842 3.359999999999707 -2.924416351440806e-13
1.5 0.6958428672226297 2.247790820476767 3.750000000002591 2.590816450265265e-12
1.6 0.6083648146160752 2.4367457662832 4.16000000000693 6.929337095437638e-12
1.7 0.5290566936740566 2.629567557533946 4.590000000005444 5.444587055508654e-12
1.8 0.4567016007712204 2.826147692171223 5.039999999998141 -1.859126134290401e-12
1.9 0.3903219460842974 3.026385585323028 5.509999999992289 -7.710951885689377e-12
2 0.3291223221286791 3.230187665709464 6.000000000002442 2.442490654175344e-12
2.1 0.2724481590078001 3.437466609237211 6.509999999999497 -5.033837929824259e-13
2.2 0.2197552692216855 3.648140684345403 7.040000000012558 1.255703093588911e-11
2.3 0.1705870545953422 3.862133188737511 7.589999999990695 -9.303704508190069e-12
2.4 0.1245572014479078 4.079371962336136 8.159999999999389 -6.104092925562909e-13
2.5 0.08133637076430866 4.299788963036583 8.75000000000226 2.259525899717119e-12
2.6 0.04064183929403394 4.523319895822285 9.360000000006586 6.585612263854124e-12
2.7 0.00222934965743236 4.749903886620089 9.98999999999781 -2.191171723231466e-12
2.8 -0.0341133655737727 4.97948319436885 10.63999999999049 -9.508873723140798e-12
2.9 -0.068571776927252 5.212002955640676 11.30999999999917 -8.249043809138712e-13
3 -0.1013087576914362 5.447410957318214 12.00000000000204 2.042810365310288e-12
3.1 -0.1324680069216879 5.685657433479092 12.71000000000636 6.363123569719242e-12
3.2 -0.1621768598101268 5.926694883278735 13.43999999999758 -2.422986290773199e-12
3.3 -0.190548610778305 6.170477907124946 14.19000000000481 4.809450580844921e-12
3.4 -0.2176844459848682 6.416963058866861 14.95999999999166 -8.343778792885281e-12
3.5 -0.2436750604884958 6.666108712048336 15.75000000000179 1.794120407794253e-12
3.6 -0.2686020190760892 6.917874938523173 16.56000000002793 2.793298058134663e-11
3.7 -0.2925389073885415 7.172223397984279 17.38999999999731 -2.686775281424136e-12
3.8 -0.3155523105139151 7.42911723765007 18.23999999999727 -2.732072380828843e-12
3.9 -0.3377026486746939 7.688520999656106 19.10999999999866 -1.342712399599044e-12
4 -0.3590448941611992 7.950400537177861 20.00000000001606 1.605826582817826e-11
4.1 -0.3796291888415436 8.214722936869059 20.91000000001309 1.309516037273362e-11
4.2 -0.3995013781846659 8.481456447739166 21.83999999999703 -2.975432400464939e-12
4.3 -0.4187034747973836 8.750570415524315 22.78999999998968 -1.031622703928647e-11
4.4 -0.4372740622184186 9.022035222085844 23.75999999999835 -1.653930464806663e-12
4.5 -0.4552486478563347 9.295822229429085 24.75000000000846 8.462563982902793e-12
4.6 -0.4726599724737711 9.571903727745777 25.76000000000549 5.494129456939945e-12
4.7 -0.4895382824037881 9.850252887298186 26.78999999996759 -3.241055340774679e-11
4.8 -0.5059115696867305 10.13084371362828 27.83999999999663 -3.369783618811795e-12
4.9 -0.5218057845044439 10.41365100589565 28.9100000000271 2.709995769456519e-11
5 -0.5372450236123233 10.69865031803113 30.00000000000084 8.384404281969182e-13
5.1 -0.5522516979121136 10.98581792253899 31.11000000000513 5.133529018541694e-12
5.2 -0.5668466818374271 11.2751307765618 32.2399999999745 -2.550141348089952e-11
5.3 -0.5810494468467916 11.56656649026647 33.39000000001808 1.807883703852653e-11
5.4 -0.5948781809801713 11.86010329704915 34.55999999999035 -9.651088955786591e-12
5.5 -0.6083498961731976 12.15572002578478 35.7499999999859 -1.409716787748039e-11
5.6 -0.6214805247781624 12.45339607461181 36.95999999999748 -2.517239888755185e-12
5.7 -0.6342850065582102 12.75311138636128 38.1900000000032 3.192966724352431e-12
5.8 -0.6467773672439603 13.05484642542658 39.43999999999583 -4.163815126023707e-12
5.9 -0.6589707896064629 13.35858215597922 40.7100000000045 4.494040556357604e-12
6 -0.670877677871321 13.66430002140698 42.00000000001459 1.459454779251246e-11
6.1 -0.6825097162058276 13.97198192491624 43.30999999998249 -1.75008098290963e-11
6.2 -0.6938779219064769 14.28161021123291 44.64000000003188 3.187313607488917e-11
6.3 -0.7049926938537755 14.59316764924931 45.9900000000318 3.180119362289346e-11
6.4 -0.715863856716369 14.90663741565324 47.36000000002589 2.588670597325482e-11
6.5 -0.726500701345836 15.222003079372 48.7499999999996 -3.979039320256561e-13
6.6 -0.7369120217414309 15.53924858691136 50.15999999993838 -6.161663193560152e-11
6.7 -0.7471061489219293 15.85835824833476 51.58999999999504 -4.958734811655319e-12
6.8 -0.7570909820130148 16.17931672400653 53.03999999998766 -1.234038565778306e-11
6.9 -0.7668740168092776 16.50210901226642 54.51000000100765 1.007648933043503e-09
7 -0.7764623720559678 16.82672043658028 55.99999999995545 -4.455102953215828e-11
7.1 -0.7858628136599484 17.15313663528092 57.50999999983604 -1.639543258102893e-10
7.2 -0.7950817770212208 17.48134355022496 59.04000000001636 1.636021179640679e-11
7.3 -0.804125387653983 17.81132741620624 60.58999999998716 -1.284043010807423e-11
7.4 -0.8129994802545112 18.14307475151896 62.15999999998124 -1.876735225558868e-11
7.5 -0.8217096163452652 18.47657234830246 63.74999999999861 -1.392663762089796e-12
7.6 -0.8302611006262054 18.81180726364275 65.3599999999301 -6.989800752088549e-11
7.7 -0.8386589961406261 19.14876681105959 66.98999999999401 -5.990798135346864e-12
7.8 -0.8469081383553058 19.487438552212 68.64000000004481 4.48103429362412e-11
7.9 -0.8550131482496721 19.82781028913469 70.30999999998798 -1.202607805006473e-11
8 -0.8629784444906156 20.16987005676574 71.99999999999801 -1.989519660128281e-12
8.1 -0.870808254770019 20.51360611569972 73.71000000008232 8.232334258728713e-11
8.2 -0.8785066263741219 20.8590069453774 75.43999999996436 -3.563073447399034e-11
8.3 -0.8860774360427158 21.20606123751556 77.18999999997149 -2.852175440271054e-11
8.4 -0.8935243991735187 21.55475788971871 78.9599999999146 -8.540559925940272e-11
8.5 -0.9008510784275988 21.90508599953461 80.75000000001202 1.20223830890609e-11
8.6 -0.9080608917744842 22.25703485853165 82.55999999995808 -4.191327840352699e-11
8.7 -0.9151571200258515 22.61059394681281 84.38999999998555 -1.443879737994536e-11
8.8 -0.9221429138912409 22.96575292760232 86.23999999998546 -1.455603693134577e-11
8.9 -0.9290213005950486 23.32250164214523 88.10999999992129 -7.872116847273958e-11
9 -0.9357951900840553 23.68083010472332 90.00000000001143 1.142552719102241e-11
9.1 -0.9424673808558298 24.04072849786763 91.9099999999938 -6.192518720027351e-12
9.2 -0.94904056543564 24.40218716784729 93.83999999989763 -1.023578027892214e-10
9.3 -0.9555173355278145 24.76519662026029 95.79000000002119 2.118070996370847e-11
9.4 -0.9619001868602525 25.12974751565342 97.7599999999716 -2.840941371040628e-11
9.5 -0.9681915237489729 25.49583066562954 99.74999999998167 -1.833200258261058e-11
9.6 -0.9743936633963083 25.86343702875129 101.7599999999859 -1.412750472162827e-11
9.7 -0.980508839945976 26.23255770679393 103.7900000000061 6.117203965594342e-12
9.8 -0.9865392083063443 26.60318394112198 105.8399999999696 -3.039403451143841e-11
9.9 -0.9924868477624008 26.97530710907296 107.9099999999854 -1.456271214728133e-11
10 -0.9983537653840405 27.34891872058871 109.9999999999955 -4.462208380573429e-12
x alpha(x) h(x) h(h(x)) h(h(x)) - x - x^2
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus
Here’s a technique for finding the first few terms of a formal power series representing the fractional iterate of a given function like $f(x)=x+x^2$. I repeat that this is a formal solution to the problem, and leaves unaddressed all considerations of convergence of the series answer.
I’m going to find the first six terms of $f^{\circ1/2}(x)$, the “half-th” iterate of $f$, out to the $x^5$-term. Let’s write down the iterates of $f$, starting with the zero-th. \begin{align} f^{\circ0}(x)&=x\\ f^{\circ1}=f&=x&+x^2\\ f^{\circ2}&=x&+2x^2&+2x^3&+x^4\\ f^{\circ3}&\equiv x&+3x^3&+6x^3& + 9x^4& + 10x^5& + 8x^6\\ f^{\circ4}&\equiv x &+ 4x^2& + 12x^3& + 30x^4& + 64x^5& + 118x^6\\ f^{\circ5}&\equiv x& + 5x^2& + 20x^3& + 70x^4& + 220x^5& + 630x^6\\ f^{\circ6}&\equiv x& + 6x^2& + 30x^3& + 135x^4& + 560x^5& + 2170x^6\\ f^{\circ7}&\equiv x& + 7x^2& + 42x^3& + 231x^4& + 1190x^5& + 5810x^6\,, \end{align} where the congruences are modulo all terms of degree $7$ and more.
Now look at the coefficients of the $x$-term: always $1$. Of the $x^2$-term? In $f^{\circ n}$, it’s $C_2(n)=n$. The coefficient of $x^3$ in $f^{\circ n}$ is $C_3(n)=n(n-1)=n^2-n$, as one can see by inspection. Now, a moment’s thought (well, maybe several moments’) tells you that $C_j(n)$, the coefficient of $x^j$ in $f^{\circ n}$, is a polynomial in $n$ of degree $j-1$. And a familiar technique of finite differences shows you that \begin{align} C_4(n)&=\frac{2n^3-5n^2+3n}2\\ C_5(n)&=\frac{3n^4-13n^3+18n^2-8n}3\,, \end{align} I won’t go into the details of that technique. The upshot is that, modulo terms of degree $6$ and higher, you have $f^{\circ n}(x)\equiv x+nx^2+(n^2-n)x^3+\frac12(2n^3-5n^2+3n)x^4+\frac13(3n^4-13n^3+18n^2-8n)x^5$.
Now, you just plug in $n=\frac12$ in this formula to get your desired series. And I’ll leave it to you to go one degree higher, using the iterates I’ve given you.