Question

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.

Answer 1

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.$$