From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Approximating a limit Date: 18 Nov 1995 05:22:56 GMT In article <48iglf$cs8@uuneo.neosoft.com>, Jack Roach wrote: > >The series SUM{1/[k(logk)^3/2]}, k=2, 3, 4, ... converges. Put another >way, the sequence 1/[2(log2)^3/2], 1/[2(log2)^3/2] + 1/[3(log3)^3/2], >1/[2(log2)^3/2] + 1/[3(log3)^3/2] + 1/[4(log4)^3/2] converges. (The >so-called "integral test" can be used to show this.) Find this limit >accurate to 3 places. That is to say if L denotes the limit, find an >approximation A so that |A - L| < .0005. Sure, it can be hard to evaluate an infinite sum. Some people make their living speeding up convergence, but in a case like this you don't need anything too fancy. You have already observed that convergence is easily determined by the integral test. Better than that, you know the integral estimates the sum. Since integral(1/(x(lnx)^(3/2)), x=2..n) differs from -2/sqrt(ln x) by a constant, this gives us a suggestion for speeding up the sum. You want to find the limit of the sequence a_n = Sum( 1/(k(ln k)^(3/2), k=2..n). With the above integral in mind I suggest we look at the sequence b_n = a_n + 2/sqrt(ln n) Clearly these sequences have the same limit as n--> oo, but the new sequence is easier to estimate. Indeed, we may write b_n = Sum( c_k, k=2..n ) where c_2 = 1/(2(ln 2)^(3/2)) + 2/sqrt(ln 2) and for k > 2 we have c_k = 1/(k(ln k)^(3/2)) + [2/sqrt(ln k) - 2/sqrt(ln(k-1))] Now it looks like we're right back where we started, only worse: I'm asking you to sum the original slowly-converging series together with another ugly one. But the terms c_k are actually much smaller, and so the series containing them converges faster. Indeed, for a fixed k let us set A = ln(k) and B = ln(1- 1/k), so that ln(k-1) = A+B = A(1+B/A). I'll write C for the fraction B/A. In terms of these constants I note c_k = 1/(k A^(3/2) ) + (2/sqrt(A))[1-(1+C)^(-1/2)]. Now, let's first toss Taylor series about wildly; we can make this precise later. The first few terms of the bracketed expression are C/2 - 3C^2/8 + ... . Also, B = -1/k - 1/(2k^2) - ..., so there is some important cancellation and c_k = 1/A^(3/2)[ -1/(2k^2) - ...] - (3/4)(1/A^(5/2))[ 1/k^2 -...] +... the dominant term of which is -1/(2A^(3/2)k^2). That is the sort of thing everyone does just to see what the real behaviour is. To justify one's steps, one needs instead to use the Taylor polynomials with the error estimates. Suffice it to say that if k is large enough, (and in this case, double digit k's are already "large enough") then the Taylor series computed above will be evaluated quite close to zero, so that the error after the 1st term is at most twice the dominant term, that is, |c_k| < 1/(A^(3/2) k^2) where A=ln k for large enough k. This makes it easy to sum lots of c_k's. Indeed, the sum of a large number of these terms starting with c_N is at most 1/( (ln N)^(3/2) ) * Sum( 1/k^2, k>=N) which is majorized by a multiple of the integral of 1/x^2 over [N-1, oo), so that Sum( c_k, k >= N ) <= 1/( (N-1) (ln N)^(3/2) ) For example, the sum of all the c_k for c >= 1000 is less than 1/20000. So we compute by hand that b_1000 is about 2.937636. So what's b_10000? Well, it's b_1000 plus the sum of the next 9000 values of c_k, which collectively add or subtract at most .00005, so we get a range of possible values. Better, _all_ remaining b_n are in this interval, so the limit of this sequence is too. This gives 2.9377 as an estimate with at least the desired accuracy for the problem of lim(a_n) = lim(b_n). For the record, here are some values of a_n and b_n: n a_n b_n 100 2.006187 2.937163 1000 2.176317 2.937636 10000 2.278655 2.937664 So we can see the b_n converging rapidly to the limit 2.93767; indeed the error is roughly proportional to 1/(N (log N)^3/2 ), as predicted above. Of course, the a_n are converging to the same limit, but as the error is about 2/sqrt(log N), it will take about 10^7000000 terms to get within 0.0005 of the true limit! dave