Closed forms for Monotonic polynomial recurrences? I have a monotonic polynomial recurrence of the following form:
c_n = 1-p + p*(c_n-1)^2
This comes from the probability that a specific branching process (Galton-Watson) will be extinct before the nth generation. It's generalization is:
c_n = 1-p_1-p_2-...-p_n + p_1(c_n-1) + p_2(c_n-1)^2 + ... + p_n(c_n-1)^n
Where p_1*1+p_2*2+...+p_n*n < 1, and c_1 << 1;
I know that polynomial recurrences have no general solution, but the monotonic case seems like it should be MUCH easier. A basic approximation for my specific c_n is easily done:
d_n = 1-c_n =1- (1-p + p*(1-c_n-1)^2)
d_n = 2p*d_n-1 - p*(d_n-1)^2 < 2p*(d_n-1) = (2p)^(n-1)*(d_1);
A cobweb plot also gives strong indication of the behavior.
My problem is, however, that although asymptotic behavior is easy to figure out, I need to be able to determine, with a fair degree of accuracy, d_i for arbitrary i. 
Is there any information out there on monotonic recurrences of polynomial form? 
Update:
Any sort of approximation that's more general and useful than mine is also useful to me.
Also, I'm only interested in real numbers. For instance, d_1 in the specific case I'm looking at is p, where p is < 0.5. Looking at cobweb plot with y = x and y = 2p*x - p*x^2 = px(2 - x), it is clear that the recurrence is monotonic and has no chaotic behavior. Is this not a strong enough of a condition to give it a (somewhat) clean form? If so, why not?
 A: In general as Qiaochu commented non-linear recurrences almost never have closed forms (your question included). On the other hand a lot can be said about your special recurrence. The substitution $d_n=\frac{1-c_n}{2}$ brings the recurrence in the form $$d_n=2pd_{n-1}(1-d_{n-1})$$
And this is known as the Logistic map 
A: A lot depends of what you mean by "fair accuracy" and on what exactly you are going to do with your formula. If a 30% upside error in each $d_n$ is tolerable, you can do the following.
We look at the recursion $d_{n+1}=qd_n(1-d_n)$ with $0<q=2p<1$ starting with some $d_1\in[0,1]$. It'll be convenient to do the first step separately, so we have $d_2=q d_1(1-d_1)$. The reason is that $q^{-1}d_2\in[0,1/4]$. Now, denote  $b_n=q^{-(n-1)}d_n$ and rewrite the recurrence as $b_{n+1}^{-1}=b_n^{-1}+q^{n-1}\frac{b_n}{b_{n+1}}$. Note now that the ratio of each term to the next is between $1$ and $4/3$ and tends to $1$, so, replacing it by $1$, we get $b_n^{-1}\approx b_2^{-1}+\frac{q-q^{n-1}}{1-q}$ with accuracy 30% and being sure that it is an underestimate. Putting all this stuff together, we get 
$$
d_n\approx q^{n-1}\left[\frac 1{d_1(1-d_1)}+\frac{q-q^{n-1}}{1-q}\right]^{-1}
$$ 
for $n\ge 2$.
Note also that 30% is a very rough estimate for the accuracy. In practice, I've never seen it being worse that 6% (though I haven't done too many simulations).
P.S. The estimate 
$$
d_n\approx q^{n-1}\left[\frac 1{d_1(1-d_1)}+\frac{q-q^{n-1}}{1-q}
+\log\left(1+d_1(1-d_1)\frac{q^2-q^{2(n-1)}}{1-q^2}\right)\right]^{-1}
$$ 
is even better (3% accuracy for small $n$ and about 0.5% accuracy for large $n$) but noticeably uglier. As several people have already mentioned, there is no exact formula, so the higher precision you want, the longer and uglier the approximation gets.
P.P.S. The main idea behind the second approximation is that if $B_n=b_{n}^{-1}$, then we make an error $q^{n-1}\frac{B_{n+1}-B_n}{B_n}\approx \frac{q^{2(n-1)}}{B_n}$ during each step that led us to the first approximation. To compensate, we would like to take the partial sums of that series. We also know that $B_n\approx \frac 1{d(1-d)}+q+q^2+\dots+q^{n-2}$. Unfortunately, we cannot sum the resulting series nicely. But if we double all the exponents in the approximate formula for $B_n$ (which will lead only to a small error when $q\approx 1$), then we'll get the Riemann sum type expression, which we can replace by the corresponding integral. Clearly, it may overshoot on the long run but to my own surprise, it not only corrects the first few terms nicely, but also corrects the asymptotics giving an error below 0.5% for large $n$ in the entire range of parameters (well, at least that is so for all values I looked at and I tried quite a few). Why it works this way remains a mystery, but it does. It can be shown rigorously that the total relative overshot coming from all steps after $n$ is at most $n^{-1}$ and I've never seen the overshots of more than 0.1% up to $n=300$. 
