From: lones@lones.mit.edu (Lones A Smith) Newsgroups: sci.math Subject: What is the solution of this recursion? Date: 8 Feb 1995 19:34:07 GMT It's simple, but nonstationary: x_{n+1}=x_n-(x_n^2)/n Is there a closed form? Even if not, how do I think about its asymptotics (but I would really LOVE a closed form). Many thanks to any samaritans, -- Lones A. Smith, Economics, MIT || The `v' in Massachvsetts Institvte E52-252C, Cambridge MA 02139 || of Technology is a Latin affectation 617-253-0914 (voice), -6915 (fax) || with which I strongly disagree. lones@lones.mit.edu (NeXT mail OK) || Feel free to svbstitvte `u' as desired. ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: What is the solution of this recursion? Date: 8 Feb 1995 22:20:28 GMT Summary: I hope x_1 is in [0,1]. In article <3hb6bf$cp5@senator-bedfellow.mit.edu>, Lones A Smith wrote: >x_{n+1}=x_n-(x_n^2)/n > >Is there a closed form? Rule of thumb: almost no recursion allows a closed form. This is especially true if we don't even know x_1 :-) >Even if not, how do I think about its asymptotics Since we've seen generating functions here lately let me mention my other favorite trick: differential equations. Suppose there were a differentiable function x = x(t) such that whenever n is an integer, x(n) = x_n. Then since in general x(t+h) is roughly x(t) + h x'(t), we'd have x_n + x'(n) roughly equal to x(n+1) = x(n) - x(n)^2/n. Subtracting gives an approximation to x'(n) (in this case, -x(n)^2/n). Well, I can certainly determine the functions x(t) for which x'(t) is actually equal to -x(t)^2/t by solving a first-order DE, in this case actually separable: -x'/x^2 = 1/t. Integrate to get 1/x = ln(t)+C, so x(t) = 1/[ln(t)+C] for some C. Now, your original function x(t) might not be very close to this one, but it tells you how to analyze your recursion; the result of your analysis is, as often as not, that x_n is close to x(n). Begin by letting y_n = 1/x_n; from the above we expect y_n to look like ln(n) + C. Sure enough, we see it satisfies the recursion [scribbles on a napkin 10 sec] y_{n+1} = y_n + (1/n) + 1/[n^2 y_n - n] Now trying y_n = z_n + ln(n), we see the z_n will need to satisfy z_{n+1} = z_n + [ 1/n - ln(1+1/n) ] + 1/[n^2 ln(n) -n + n^2 z_n ] At this point I'd make a quick estimate: if, say, |z(n)| < (1/2) ln(n) for a large n, then y_n > (1/2) ln(n), and the last big denominator is at least (n^2/2)ln(n) - n , which will surely be bigger than n^2 if n is large enough. Thus |z_{n+1}| < |z_n| +[ 1/n - ln(1+1/n)] + 1/n^2 < |z_n| + 2/n^2 < <(1/2)[ ln(n) + 4/n^2 ] < (1/2) ln(n+1). This gives us a size-bounding condition that will propogate for all further n. Then return to the recurrence equation to see that for all further n, z_{n+1} = z_n + [1/n - ln((n+1)/n)] +(error < 1/n^2). Adding these for n = n0,...,n=n1 gives z_{n1+1} = z_{n0} + [1/n0 + ... + 1/n1 - ln(n1) + ln(n0)] + error where the error is always less than Sum(1/n^2) = pi^2/6. Now you can even take a limit as n1 -> oo and find that all further z_n stay a bounded distance away from z_{n0} + ln(n0); indeed, it's not hard to show that the z_n actually converge to a constant C. Working backwards, you find indeed that x_n is roughly 1/[ln(n) + C], in a sense that can be made precise. Actually, once you know that the z_n are in fact bounded (rather than being at worst ln(n)/2 ) you can go back and improve your estimates so as to get a better sense of the limit C and how rapidly you approach it. Of course there is the nagging question of making sure the z_n are sufficiently small in the first place. This will depend on the starting point for the recursions. From x_{n+1} = x_n - x_n^2 / n it's easy to see that if x_1=0 or 1, x_n=0 for all n>1 if x_1<0 then the x_n decrease to -oo if x_1>1 then x_2<0 and the above holds if 0 -oo, I'd let y=1/x again and look at the recursion for y with an eye towards what happens with the assumption y<0 and y --> 0. There's a differential equation you can try here, which should model y_n pretty well since both y--> 0 and y' --> 0, but it's not pretty. It comes to (ty-1)dy-ydt=0; an integrating factor is 1/(ye^y), and the solution is given implicity by F(t,y)=constant, where F(t,y)= t/e^y + int(1/ye^y)dy. There is no closed form for this last integral (essentially the function maple calls Ei ). But roughly I'd estimate the relation between y_n =1/x_n and n is n/e^y + int(1/ye^y)dy = C for some constant C. dave ============================================================================== From: lasmith@athena.mit.edu (Lones A Smith) Newsgroups: sci.math Subject: Re: What is the solution of this recursion? Date: 9 Feb 1995 01:57:01 GMT In article <3hbg3c$eg1@mp.cs.niu.edu> rusin@washington.math.niu.edu (Dave Rusin) writes: >In article <3hb6bf$cp5@senator-bedfellow.mit.edu>, >Lones A Smith wrote: >>x_{n+1}=x_n-(x_n^2)/n >> >>Is there a closed form? >Rule of thumb: almost no recursion allows a closed form. This is >especially true if we don't even know x_1 :-) >dave That's what happens when you're friend is telling you "Come on, let's go; I'm late!". I should have noted x_0=1/2. Pretty silly on my part...... Lones -- Lones A. Smith, Economics, MIT || The `v' in Massachvsetts Institvte E52-252C, Cambridge MA 02139 || of Technology is a Latin affectation 617-253-0914 (voice), -6915 (fax) || with which I strongly disagree. lones@lones.mit.edu (NeXT mail OK) || Feel free to svbstitvte `u' as desired.