Re: Evaluate the following limit

In article <aderamey.addw-8FC39F.21152110082008@xxxxxxxxxxxxxxxxxxxxxx>,
The World Wide Wade <aderamey.addw@xxxxxxxxxxx> wrote:
In article <g7ktd5$6iqi@xxxxxxxxxxxxxxxxxxxx>,
hrubin@xxxxxxxxxxxxxxxxxxxx (Herman Rubin) wrote:

In article <489de860$0$20717$9b4e6d93@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
karl <oudeis@xxxxxxxxxxx> wrote:
T-Hope schrieb:
This has been posted on a forum and is bugging me. I appreciate any
help. I'm sure the OP of the problem would too.



[ infty ]^(1/n)
lim [ ---- n^k ]
n->infinity [ \ ------------------- ]
[ / (k+1)^{k+1} ]
[ ---- ]
[ k=0 ]

-T


Look at it, so nobody can understand it.

Nobody? There is not too much difficulty in doing the
problem, if one knows what is involved in getting an
asymptotic approximation of the sum.

Hint: A sum is approximated by an integral.

At first I didn't quite get what you were hinting at. Is the below
what you had in mind?

Replacing the above series with sum(k=1,oo) n^k/k^k, the resulting
expression is

{ n * sum(k=1,oo) [(k/n)^(-k/n)]^n * (1/n) }^(1/n) (1)

Now n^(1/n) -> 1, so forget about the first n inside the { }. The sum
in (1) looks very much like a Riemann-type sum for an integral. In
other words, it's reasonable to expect (1) to be very close to

{int_[0,oo) [x^(-x)]^n dx}^(1/n) (2)

for n large. By standard L^p theory, (2) approaches the maximum value
of x^(-x) on [0,oo) as n -> oo. Easy calulus shows that max is e^(1/e).

So that's another way to get the limit assuming one can show the
difference between (1) and (2) -> 0 as n -> oo. That shouldn't be too
hard.

Since x^{-x} is monotonic increasing when x < 1/e and monotonic
decreasing when x > 1/e, we can control the difference between the
sum and integral by shifting one segment in the partition of the
Riemann-type sum.

The asymptotic expansion for the integral can be derived as follows

oo
1 --- n k
- > ( - )
n --- k
k=1

1 |\oo n x
~ - | ( - ) dx [ z = x/n gives the integral in (2) ]
n \| 0 x

1 |\oo
= - | exp( -x log(x/n) ) dx [1]
n \| 0

The error should be less than the sum of the integral over [0,1] and
the integral over [floor(n/e),floor(n/e)+1]. The integral on [0,1]
is less than 1. The integral on the other interval is approximately
1/n exp(n/e), which is obviously the major error term.

The integrand in [1] is stationary when x/n = 1/e. Therefore, we
try to take advantage of this by making the substitution 1+u = ex/n
so that we get

-x log(x/n)

= -n(1+u)/e (log(1+u)-1)

= n/e (1+u) (1-log(1+u))

= n/e (1+u) (1 - u + u^2/2 - u^3/3 + u^4/4 - ...)

= n/e (1 - u^2/2 + u^3/6 - u^4/12 + u^5/20 - ...)

n n u^3 u^4 u^5 (-u)^k
= - - -- (u^2 - --- + --- - --- + ... + ------ + ... ) [2]
e 2e 3 6 10 C(k,2)

Therefore,

1 |\oo
- | exp( -x log(x/n) ) dx
n \| 1

1 |\oo n
= - exp(n/e) | exp( - -- v^2 ) du
e \|e/n-1 2e

where v^2 = u^2 - u^3/3 + u^4/6 - u^5/10 + ... + (-u)^k/C(k,2) + ...

Inverting the power series for v^2, we get

u = v + v^2/6 - v^3/72 + v^4/270 - 23v^5/17280 + ...

du = (1 + v/3 - v^2/24 + 2v^3/135 - 23v^4/3456 + ...) dv

Thus, we get the asymptotic expansion of the integral to be

1 |\oo
- | exp( -x log(x/n) ) dx
n \| 1

1 |\oo n v v^2 2v^3 23v^4
= - exp(n/e) | exp(- -- v^2) (1 + - - --- + ---- - ----- + ...) dv
e \|-sqrt(2) 2e 3 24 135 3456

1 |\oo n v^2 23v^4
~ - exp(n/e) | exp(- -- v^2) (1 - --- - ----- - ...) dv
e \|-oo 2e 24 3456

1 |\oo 2e v^2 4e^2 23v^4
= - exp(n/e) sqrt(2e/n) | exp(-v^2) (1 - -- --- - ---- ----- - ...) dv
e \|-oo n 24 n^2 3456

1 2e Gamma(3/2) 4e^2 23 Gamma(5/2)
= - exp(n/e) sqrt(2e/n) (Gamma(1/2) - -- ---------- - ---- ------------- - ...)
e n 24 n^2 3456

= exp(n/e) sqrt(2pi/(en)) (1 - 1/24 (e/n) - 23/1152 (e/n)^2 - ...)

Of course, the error between the sum and the integral I estimated
above, 1/n exp(n/e), is between the lead and second terms in the
asymptotic expansion for the integral. Thus, after working through
the asymptotic expansion for the integral, it does not apply to the
sum past the first term.

In any case, the sum is asymptotically exp(n/e) sqrt(2pi/(en)) and
the limit of the n^{th} root is exp(1/e).

Rob Johnson <rob@xxxxxxxxxxxxxx>
take out the trash before replying
to view any ASCII art, display article in a monospaced font
.

Relevant Pages

  • Re: Need help with infinite series
    ... > The expected error in the sum of 10^9 terms would be ... > digits. ... > can derive the asymptotic expansion for the ...
    (sci.math)
  • Re: summary of {1/n}
    ... I'm guessing that by summary, ... is not exact, ... where gamma is the Euler-Mascheroni constant ... The asymptotic expansion is ...
    (sci.math)
  • Re: ? approximates in different subspaces
    ... That person said that this approximation is spanned by {c, inv*c, ..., ... then taking V as the span of the k eigenvectors to the k algebraically largest, ... first k Lanczos vectors from Lanczos combined with inverse iteration ...
    (sci.math.num-analysis)
  • Re: how to evaluate the addition of millions of functions dynamically and efficiently?
    ... monitor, I assume that your grid is uniform. ... and y so that the grid consists of integer values only (a lattice sum). ... Both sums can be computed in closed form -- they turn out to be ... approximation will be excellent near the center of the monitor and will ...
    (sci.math.symbolic)
  • Re: how to evaluate the addition of millions of functions dynamically and efficiently?
    ... monitor, I assume that your grid is uniform. ... and y so that the grid consists of integer values only (a lattice sum). ... Both sums can be computed in closed form -- they turn out to be ... approximation will be excellent near the center of the monitor and will ...
    (sci.math.num-analysis)