## Closed form of a nonlinear recurrence sequence.

The master theorem seems to fail on nonlinear recursive functions. Is there a standard tool for finding the closed forms of recursive functions of this form?

The question comes from trying to find the closed form of the following recursive function: $f_i(X) = (f_{i-1}(X)^2 + f_{i-1}(X))/2$
Where:
$f_0(X) = X$

I would be willing to part with recurrence relations for this function, but I would be much more delighted to learn a general method or trick which makes finding closed forms of functions like this simple.

-
I think you may want to retitle this something like "Closed form for a nonlinear recurrence sequence?" – Zev Chonoles Jan 21 2010 at 3:08
Generally speaking, nonlinear recurrences almost never have closed forms. – Qiaochu Yuan Jan 21 2010 at 3:28
I changed the title as suggested. – Jason Knight Jan 21 2010 at 3:29
Qiaochu is right. Whatever general results there are for nonlinear recurrences, they should be in here: books.google.com/… I own this book myself, but have only studied the parts of it relevant to linear recurrences, so I can't direct you to anything specific. – Zev Chonoles Jan 21 2010 at 3:39
Seems like I'm out of luck. I just compared the function in question with logistic maps (the similarity is striking). No wonder I was butting my head against a wall. – Jason Knight Jan 21 2010 at 3:50

As has already been explained, there is no hope in general of finding explicit solutions to nonlinear recurrences. However, for your example, it is possible to find $\lim_{n\to\infty}f_n(X)$ for all real $X$.
The function $g(x)=(x^2+x)/2$ has two fixed points: $x=0$ (atractor) and $x=1$ (repulsor). Its respective stable sets are $(-2,1)$ and $\{-2,1\}$; $(-\infty,-2)\cup(1,+\infty)$ is the stable set of $+\infty$. Thus,
$$\lim_{n\to\infty}f_n(X)=\left\{\matrix{0, & X\in(-2,1)\cr 1, & X\in\{-2,1\}\cr +\infty, & X\in(-\infty,-2)\cup(1,+\infty)}\right.$$