# A Limit of a sum related to the exponential series.

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?

-
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

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}$$

-