Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
I think you may want to retitle this something like "Closed form for a nonlinear recurrence sequence?" –  Zev Chonoles Jan 21 '10 at 3:08
3  
Generally speaking, nonlinear recurrences almost never have closed forms. –  Qiaochu Yuan Jan 21 '10 at 3:28
    
I changed the title as suggested. –  Jason Knight Jan 21 '10 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 '10 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 '10 at 3:50
show 4 more comments

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.