Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So my question is to evaluate, $\lim_{n\to\infty} n^ne^{-n}\sum_{k=1}^{\infty}\frac{n^k}{(n+k)!}$

What I've done so far is, $\lim_{n\to\infty} n^ne^{-n}\sum_{k=1}^{\infty}\frac{n^k}{(n+k)!} $

$=\lim_{n\to\infty} n^ne^{-n}\frac1{n!}\sum_{k=1}^{\infty}\frac{n^k}{(n+1)(n+2)..(n+k)}$

$=\lim_{n\to\infty} \frac1{\sqrt{2\pi n}} \sum_{k=1}^{\infty}\frac{1}{(1+\frac1n)(1+\frac2n)..(1+\frac k n)}$

$=\lim_{n\to\infty} \frac1{\sqrt{2\pi n}} \sum_{k=1}^{n}\frac{1}{(1+\frac1n)(1+\frac2n)..(1+\frac k n)}$

(The rest of the sum is bounded.)

And then, I'm stuck. Any ideas?

share|improve this question
    
You can truncate the sum much further than you have so far, and then try relating the sum to an integral, but something makes me suspect there is a much simpler approach. –  Sean Eberhard Feb 22 '13 at 11:49
    
If you screw up your face and look at the first formula from just the right angle, you'll notice that it's precisely the probability that a Poisson-distributed random variable X with parameter n takes a value larger than n. So this question is about the median of a Poisson distribution. :) –  Sean Eberhard Feb 22 '13 at 11:58
    
@SeanEberhard Yeah, for example, $k/(n+k)\le\ln(1+k/n)\le k/n$. –  Frank Science Feb 22 '13 at 11:59

1 Answer 1

up vote 1 down vote accepted

Your sum is related to one given in D.E. Knuth, The Art of Programming, vol. 1, Sec. 1.2.11.3. There he defines

$$R(n) = \sum_{k=0}^{\infty} \frac{n! n^k}{(n+k)!}$$

Your expression, call it $S(n)$, is $(n^n e^{-n}/n!) R(n)$.

He shows, in fact, that $R(n)$ is related to an incomplete gamma function $\gamma(x,a)$:

$$e^x \gamma(x,a) = \sum_{k=0}^{\infty} \frac{x^{k+a}}{a (a+1)\ldots(a+k)} $$

$$R(n) = \frac{n! e^n}{n^n} \frac{\gamma(n,n)}{(n-1)!} \implies S(n) = \frac{\gamma(n,n)}{\Gamma(n)}$$

The derivation of the asymptotic expansion of $R$ given in Knuth is long and absolutely worthwhile reading, but I will not reproduce it here. The result is that

$$R(n) = \sqrt{\frac{\pi n}{2}} + \frac{1}{3} + O\left(n^{-1/2}\right)$$

From Stirling,

$$\frac{n^n}{n! e^n} \sim \frac{1}{\sqrt{2 \pi n}} \;\;\; (n \rightarrow \infty)$$

Therefore,

$$\lim_{n \rightarrow \infty} S(n) = \frac{1}{2}$$

share|improve this answer

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.