From: [Permission pending] Newsgroups: sci.math Subject: Re: Asymptotic behavior of sequence? Date: 19 Apr 1995 14:31:26 GMT In article <3muobi$if3@cat.cis.Brown.EDU>, jpf@hydra.cfm.brown.edu (Jim P. Ferry) writes: >What is the asymptotic behavior of the following sequence f? > > n > f(n) = Sum (i-n)^i > i=0 > >The sequence begins: > >1, 1, 0, 0, 1, -1, 0, 6, -19, 29, 48, -524, 2057, -3901, -9632, 129034, >-664363, 1837905, 2388688, -67004696, 478198545, -1994889945 > >(This was posted before as a "determine the next number" problem under the > heading "Sequence Stickler". There were no responses.) > >Three specific questions are: > >a) What is the pattern of the plus and minus signs? > >b) What is a bound on |f(n)|? > >c) What is an optimal bound on |f(n)|? By Poisson summation formula it is found that f(n) = 1/2+2 NIntegrate[(n-t)^t Cos[Pi t],{t,0,n}] to very good approximation. By using saddle point method we can evaluate this integral approximately. The saddle point is best obtained via numerical method, otherwise the result will only be good for extremely large n. In the latter case the following formula can be simplified. From this once can determine the sign pattern, etc. Numerical verification (s[n] = f(n), u[n] denote numerical integration and v[n] denotes saddle point result): Mathematica 2.2 for Solaris Copyright 1988-93 Wolfram Research, Inc. -- Open Look graphics initialized -- In[1]:= s[n_]:=Sum[(-1)^i (n-i)^i,{i,0,n-1}] In[2]:= u[n_]:=1/2+2 NIntegrate[(n-t)^t Cos[Pi t],{t,0,n}] In[3]:= v[n_]:=Module[{x}, x=x/.FindRoot[x==1/(1-I Pi+Log[n x]),{x,1/Log[n]}]; N[1/2+2n Re[Sqrt[2Pi x/(n(1+1/x))]E^((x+1/x-2)n)]]] In[4]:= Table[{n,s[n],u[n],v[n]},{n,5,20}]//TableForm Out[4]//TableForm= 5 -1 -0.925444 -0.640792 6 0 0.0836419 0.352523 7 6 6.09113 6.40387 8 -19 -18.9038 -18.5659 9 29 29.1007 29.1989 10 48 48.1063 48.9158 11 -524 -523.889 -523.844 12 2057 2057.11 2053.65 13 -3901 -3900.88 -3879.16 14 -9632 -9631.88 -9693.78 15 129034 129034. 129062. 16 -664363 -664363. -663462. 6 6 17 1837905 1.83791 10 1.83157 10 6 6 18 2388688 2.38869 10 2.41296 10 7 7 19 -67004696 -6.70047 10 -6.70318 10 8 8 20 478198545 4.78199 10 4.7778 10 One can see from the above that the approximation is not bad at all. [sig deleted - djr] ============================================================================== [I wrote asking for more information about this method and got this:-- djr] ============================================================================== Date: Wed, 19 Apr 95 13:41:02 EDT From: [Permission pending] To: rusin@math.niu.edu Subject: Re: Asymptotic behavior of sequence? > From rusin@math.niu.edu Wed Apr 19 12:19:07 1995 > Date: Wed, 19 Apr 95 11:13:41 CDT > From: rusin@math.niu.edu (Dave Rusin) > To: [Permission pending] > Subject: Re: Asymptotic behavior of sequence? > Newsgroups: sci.math > Organization: Northern Illinois University, Math > Cc: > Content-Length: 915 > > In article <[Identifier deleted]> you write: > >By Poisson summation formula it is found that > > I'm with you so far > > >to very good approximation. By using saddle point method we can > >evaluate this integral approximately. The saddle point is best > >obtained via numerical method, otherwise the result will only be > >good for extremely large n. In the latter case the following formula > >can be simplified. From this once can determine the sign pattern, etc. > > OK, I don't usually have to actually _compute_ integrals very often. > Can you mention a good reference for the saddle-point method? The Mma > code you included doesn't give me a clear idea of what it's supposed > to do. > > From your analysis, can you in fact predict the sign of f(n)? I was > thinking it would, for example, depend on the parity of the integer > part of e*n (e=2.718..) since that's related to the location of > the largest term in the sum. > > dave > Dave, Any textbook dealing with asymptotics will have to mention saddle point method. Check out for example, Copson, Jeffereys, Erdelyi and a dozen others. In fact, there are so many of them that I don't know which one to name (decisions, decisions :)) Actually the idea is very simple. Let't me try to explain it to you in a few lines for a real integral. Given an integral Integrate[f[x]E^(z g[x]),{x,a,b}] for z large real. If the integral converges and g'[c] = 0 for a < c < b. Then it is easy to see that g[x] = g[c]+g''[c](x-c)^2 will be a good approximation to the phase function. When z is large, it is safe to ignore higher order terms AND approximate f[x] by f[c]. So the approximation formula is f[c] E^(z g[c]) Sqrt[2 Pi/(-g''[c])]. If c lies in the complex plane, the analysis is more or less the same if one deforms path via Cauchy integration formula. This is what I use in the Mma code: v[n_]:=Module[{x}, x=x/.FindRoot[x==1/(1-I Pi+Log[n x]),{x,1/Log[n]}]; N[1/2+2n Re[Sqrt[2Pi x/(n(1+1/x))]E^((x+1/x-2)n)]]] Here x is nothing but the saddle point c. The find root simply finds the point where g'[x] vanishes. (Asymptotically the saddle point is at c = 1/Log[n], but this is good only for extremely large n where the function value is so large as of no interest.) The next line just implements the above approximation formula. The detection of signs depends on argument reduction of course. Just like given w, we ask what is the sign of Sin[w]. This will require us to get wbar = Mod[w,2Pi] and check if wbar lies in [0, Pi]. This reduction is feasible for large w only if we use Pi to very high accuracy. For example, if you ask Sin[10^1000] in Mma via N[Sin[10^1000,1000] (with 1000 digits!) you will get garbage. But things will be ok if you replace 1000 digits by 1010 digits, say. In this sense the sign pattern can be determined. If you think this is too expensive, then the same thing can be said for the simplest function Sin[x]. Weird, isn't it? Regards [sig deleted -- djr] ============================================================================== Date: Thu, 20 Apr 95 10:40:33 CDT From: rusin (Dave Rusin) To: rusin Subject: Unmailed letter [A started, but unmailed, post/letter -- some bogus reasoning developed] In one article, jpf@hydra.cfm.brown.edu (Jim P. Ferry) writes: >What is the asymptotic behavior of the following sequence f? > n > f(n) = Sum (i-n)^i > i=0 > >Three specific questions are: >a) What is the pattern of the plus and minus signs? >b) What is a bound on |f(n)|? >c) What is an optimal bound on |f(n)|? In a follow-up article [Permission pending] wrote: >By Poisson summation formula it is found that > >f(n) = 1/2+2 NIntegrate[(n-t)^t Cos[Pi t],{t,0,n}] > >to very good approximation. By using saddle point method we can >evaluate this integral approximately. [This person] was good enough to explain this to me in email; the method essentially allows the maximum value of the integrand to determine the value of the integral. With this in mind, it's clear how to estimate the signs and magnitude of f(n). It's a little easier to write f(n) = (-1)^n Sum( k^(n-k) . (-1)^k ) since the kth summand is then exp( (n-k) ln(k) ). The function (n-x) ln(x) hits its maximum when x=x0, where ln(x0) = (n/x0) - 1. (This is about the same as the solution to x0 ln(x0) = n, which is very roughly x0 = n/ln(n) ) Rounding up and rounding down give the two candidates for the maximum term in the sum. Once the maximum term a_k is found, we can easily bound the value of (-1)^k * f(n). On the one hand, the value is less than the largest term in the sum, since the total value is ... - (a_{k-1}-a_{k-2}) + a_k - (a_{k+1}-a_{k+2}) - ... and all the paired summands are positive (within the parentheses). Likewise, we can get a lower bound on the value by grouping the succesive terms the other way: it's at least a_k - (a_{k-1} + a_{k+1}) . In particular, the sign of this value (that is, (-1)^k times the sign of the sum) is positive as long as the two neighboring terms are sufficiently small. The tricky case is when the maximal x is nearly midway between two integers. Writing g(x) = (n-x) log(x) we can compute its Taylor series around the maximal x=x0; g(x) = g(x0) + g''(x0)/2 * (x-x0)^2 + C, where C = (1/6)(x-x0)^3 * g'''(w) for some w between x0 and x. Since g'''(x) = (x+2n)/x^3, this C is (for the two x closest to x0) less than (log n)^3/(2n^2) except perhaps for the smallest n's. In particular, we can tell which of the a_k is larger: as long as one of the values of g''(x0)/2 *(x-x0)^2 exceeds the other by (log n)^3/n^2 or more, that value of x will lead to the larger a_k. Writing the values of x as x0 - e and x0 + (1-e), it seems that the natural choice (for which of these two leads to the larger a_k) is in fact the correct one as long as e differs from (1/2) by at least logn/n. >One can likewise show that, staying about this far away from 1/2, we >can keep the largest term at least twice as big as its neighbors, and >thus larger than its sum. [BOGUS!] [Unfortunately, the neighboring terms tend to diminish by computable ratios nearby, which ratios tend to 1, not 0.] In conclusion, we find that the sign of (-1)^k f(n) is positive as long as the solution x0 to log(x) = (n/x) - 1 is closer to k than to any other integer, and not closer than log(n)/n or so to a half integer. In particular, the sign of f(n) changes very nearly at those values of n for which the solution x0 is of the form k-(1/2) for an integer, that is, the sign changes to (-1)^k when n gets past ( k- 1/2 )* ( log( k - 1/2 ) + 1 ). I'm guessing that someone better versed in transcendental number theory can show that x0 must stay a "reasonable" distance away from half-integers, possible at least log(n)/n away, so that the method for determining sign changes, above, is correct on the nose. The above method of proof should also allow an estimate of the magnitude of f(n): the ratio of |f(n)| to exp( (n-x0)*log(x0) ) = exp( (n-x0)^2/x0 ) is less than 1, as noted above, and can be bounded below by some expression involving n as long as x0 is bounded away from 1/2. > 8 8 > 20 478198545 4.78199 10 4.7778 10 > [For n=20, n/logn=6.76, x0= 6.84207911 (quite far from a half-integer); exp((n-x0)log x0) = 9.75 x 10^10 and the largest terms is indeed 7^13=9.689x10^10. But the neighboring terms are 6^14=7.836 x 10^10 and 8^12=6.87 x 10^10, which are much closer to the largest term than any of them are to the net sum.] ==============================================================================