1
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ I think you may want to retitle this something like "Closed form for a nonlinear recurrence sequence?" $\endgroup$
    – Zev Chonoles
    Commented Jan 21, 2010 at 3:08
  • 3
    $\begingroup$ Generally speaking, nonlinear recurrences almost never have closed forms. $\endgroup$
    – Qiaochu Yuan
    Commented Jan 21, 2010 at 3:28
  • $\begingroup$ I changed the title as suggested. $\endgroup$
    – Jason Knight
    Commented Jan 21, 2010 at 3:29
  • $\begingroup$ 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. $\endgroup$
    – Zev Chonoles
    Commented Jan 21, 2010 at 3:39
  • $\begingroup$ 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. $\endgroup$
    – Jason Knight
    Commented Jan 21, 2010 at 3:50

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .