Closed form of a nonlinear recurrence sequence. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T09:47:05Z http://mathoverflow.net/feeds/question/12484 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/12484/closed-form-of-a-nonlinear-recurrence-sequence Closed form of a nonlinear recurrence sequence. Jason Knight 2010-01-21T02:26:43Z 2010-01-21T14:02:48Z <p>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?</p> <p>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$<br> Where:<br> $f_0(X) = X$</p> <p>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.</p> http://mathoverflow.net/questions/12484/closed-form-of-a-nonlinear-recurrence-sequence/12541#12541 Answer by Julián Aguirre for Closed form of a nonlinear recurrence sequence. Julián Aguirre 2010-01-21T14:02:48Z 2010-01-21T14:02:48Z <p>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$.</p> <p>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,</p> <p>$$\lim_{n\to\infty}f_n(X)=\left\{\matrix{0, &amp; X\in(-2,1)\cr 1, &amp; X\in\{-2,1\}\cr +\infty, &amp; X\in(-\infty,-2)\cup(1,+\infty)}\right.$$</p>