Asymptotics of iterated polynomials Let the sequence $u_1, u_2, \ldots$ satisfy $u_{n+1} = u_n - u_n^2 + O(u_n^3)$.  Then it can be shown that if $u_n \to 0$ as $n \to \infty$, then $u_n = n^{-1} + O(n^{-2} \log n)$.  (See N. G. de Bruijn, Asymptotic methods in analysis, Section 8.5.)
This can be used to obtain asymptotics for $v_{n+1} = Av_n - Bv_n^2 + O(v_n^3)$, where $A$ and $B$ are constants.  Let $w_n = A^{-n} v_n$; this gives
$$ A^{n+1} w_{n+1} = A^{n+1} w_n - B A^n w_n^2 + O(A^n w_n^3)$$
and so
$$ w_{n+1} = w_n - BA^{-1} w_n^2 + O(w_n^3). $$
Then let $w_n = Ax_n/B$ to get
$$ Ax_{n+1}/B = Ax_n/B - B/A \cdot (Ax_n/B)^2 + O(x_n^3) $$
and after simplifying
$ x_{n+1} = x_n - x_n^2 + O(x_n^3)$.  This satisfies the initial requirements for $u_n$ (with some checking of the side condition); then substitute back.
But say I actually know that $u_{n+1} = P(u_n)$ for some polynomial $P$, with $P(z) = z - z^2 + a_3 z^3 + \cdots + a_d z^d.$   In this case it seems like it should be possible to get more explicit information about $u_n$.  Is there a known algorithm for computing an asymptotic series for $u_n$ as $n \to \infty$?
 A: Have you tried the method of section 8.7, i.e., solving Abel's equation $\phi(P(x))-\phi(x)=1$? Here we expect $\phi(t)=t^{-1}+\sum_{n=1}^{\infty}c_n t^n$, and you can find the coefficients of $\phi$ one by one. For example, I took $P(x)=x-x^2+x^3+x^4$ and immediately found $c_1=-2$, $c_2=-5/2$, $c_3=-7/2$, $c_4=-17/4$...  Not a general formula, but you can get as many terms as you want for a given $P$.
A: As explained above by 002, solving Abel equation is indeed the key. Using the language of holomorphic dynamics, people would say that you are studying the dynamics of a polynomial near the parabolic fixed point $z=0$.
By a simple linear change of variables, the study of any such parabolic fixed point can be reduced to the study of $z \mapsto z+z^{2}+O(z^3)$. Then you can apply another change $w=-\frac{1}{z}$. Thus you are reduced to the study of $f(w)=w+1+O(1/w)$. If the real part $Re(w)$ is large enough you will obtain $f^{n}(w)=w+n+O(\log n)$. This will give you what you want (when going back to the z-variable).
The domain $Re(w)>R$ (for large $R$) looks like some kind of cardioid (in your particular case) when you visualize it in the z-variable (it's poetically called an attracting petal). 
All this material is explained in details in several books. One great example is the book by John Milnor on Complex dynamics. Here is a free (earlier) version:
http://www.math.sunysb.edu/cgi-bin/preprint.pl?ims90-5
So in summary the key words you should look for are: parabolic fixed point, Fatou coordinates, Leau-Fatou flower theorem (the last one describing those "petals")...
