# Challenge X: French fish

1. Aug 18, 2013

### micromass

Staff Emeritus
Find the following limit:

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

2. Aug 19, 2013

### Mandelbroth

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?

Last edited: Aug 19, 2013
3. Aug 19, 2013

### Staff: Mentor

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.

Last edited: Aug 19, 2013
4. Aug 19, 2013

### micromass

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

5. Aug 19, 2013

### 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.

6. Aug 19, 2013

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

7. Aug 19, 2013

### micromass

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

8. Aug 20, 2013

### micromass

Staff Emeritus
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!