What is the Limit of e^-n times n^k over k! for n Approaching Infinity?

[micromass]

Find the following limit:

$$\lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^n \frac{n^k}{k!}$$

 

[Mandelbroth]

Find the following limit:

$$\lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^n \frac{n^k}{k!}$$

I have the vaguest feeling that the limit is 1. I'm too tired to prove it right now. I'll get back to it soon. :tongue:

Edit: Probably not. Looking at it now, as shown below, it is an upper bound. Taking the expansion out a couple terms, it looks like it's less than 0.6.

Why is this called french fish? Is this hinting at using something by Poisson?

 

[mfb]

Well, 1 is an upper limit:
$$\lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^n \frac{n^k}{k!} \leq \lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^\infty \frac{n^k}{k!} = \lim_{n\rightarrow +\infty} 1 = 1$$

It is interesting that
$$\lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^n \frac{n^k}{k!} = \lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^{n-1} \frac{n^k}{k!}$$ but I am not sure how to convert this to a lower limit on the limit.

Edit: Okay, that approach does not work. And the limit is not 1. I guess 1/2.

The question can be re-phrased as "in a Poisson distribution with expectation value n, what is the probability to get at most the expectation value?" - and then the limit of n->infinity. As the Poisson distribution approaches a Gaussian distribution, I would expect 1/2 as limit.

 

[micromass]

Well, 1 is an upper limit:
$$\lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^n \frac{n^k}{k!} \leq \lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^\infty \frac{n^k}{k!} = \lim_{n\rightarrow +\infty} 1 = 1$$

It is interesting that
$$\lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^n \frac{n^k}{k!} = \lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^{n-1} \frac{n^k}{k!}$$ but I am not sure how to convert this to a lower limit on the limit.

Edit: Okay, that approach does not work. And the limit is not 1. I guess 1/2.

The question can be re-phrased as "in a Poisson distribution with expectation value n, what is the probability to get at most the expectation value?" - and then the limit of n->infinity. As the Poisson distribution approaches a Gaussian distribution, I would expect 1/2 as limit.

Right. The limit is indeed 1/2. And an application of the central limit theorem gives the answer. Well done!

 

[chingel]

I worked out that the limit is less than or equal to 0.5:

Reversing it and using the Taylor series for e:
$$\frac{e^{n}}{ \sum_{k=0}^n \frac{n^k}{k!}}=1+\frac{\sum_{k=n+1}^\infty \frac{n^k}{k!}}{ \sum_{k=0}^n \frac{n^k}{k!}}$$
Introducing $x=\frac{n^n}{n!}$
$$\frac{\sum_{k=n+1}^\infty \frac{n^k}{k!}}{ \sum_{k=0}^n \frac{n^k}{k!}}=\frac{x \frac{n}{n+1}+x \frac{n}{n+1} \frac{n}{n+2}+...}{x+x+x\frac{n-1}{n}+x\frac{n-1}{n}\frac{n-2}{n}+...}=\frac{\frac{n}{n+1}+\frac{n}{n+1} \frac{n}{n+2}+...}{2+\frac{n-1}{n}+\frac{n-1}{n}\frac{n-2}{n}+...}$$
The number of terms in the numerator is infinity, the denominator goes until the terms reach zero. For very large n we have a lot of terms close to 1, so we can neglect the 2. Since $\frac{n}{n+a} > \frac{n-a}{n}$ and replacing some of the terms in the numerator like that to get a 1 the result is:
$$\frac{\frac{n}{n+1}+\frac{n}{n+1} \frac{n}{n+2}+...}{\frac{n-1}{n}+\frac{n-1}{n}\frac{n-2}{n}+...}>1+\frac{\sum_{k=1}^\infty \frac{(n)!n^k}{(2n+k)!}}{\frac{n-1}{n}+\frac{n-1}{n}\frac{n-2}{n}+...}$$
For large n the numerator of the second term goes to zero.

When I discarded the 2, maybe the denominator and numerator are quite equal, their difference is small and the 2 makes the denominator actually bigger. But in the limit it should be negligible, so the limit of the reciprocal is 2 or larger and the limit of the original expression is 0.5 or smaller.

 

[lurflurf]

You really like Obfuscation.
since
$$e^{-n} \sum_{k=0}^n \frac{n^k}{k!}=\left( 1+ \gamma(n+1,n)/\Gamma(n+1,n) \right)^{-1}$$
Why not just ask
$$\lim_{n\rightarrow \infty} \gamma(n+1,n)/\Gamma(n+1,n)=\lim_{n\rightarrow \infty} \int_0^n t^n e^{-t} \mathrm{d}t {\huge/} \int_n^\infty t^n e^{-t} \mathrm{d}t=1$$

 

[micromass]

You really like Obfuscation.

You don't seem to grasp the concept of a challenge :tongue:

 

[micromass]

Well done by mfb for finding the solution. The (partial) solution by chingel is also very nice!

And a special thanks to lurflurf for showing another neat interpretation of this problem!