## Closed form of a nonlinear recurrence sequence.

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

3
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
show 4 more comments

## 1 Answer

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 11, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9607197642326355, "perplexity_flag": "middle"}