15
$\begingroup$

Possible Duplicate:
Compute the limit: $\lim_{n\rightarrow\infty} e^{-n} \sum\limits_{k=0}^{n} \frac{n^k}{k!}$

I want to calculate the following:

$$ \lim_{n \rightarrow \infty} \left( e^{-n} \sum_{i = 0}^{n} \frac{n^i}{i!} \right) $$

Numerical calculations show it has a value close to 0.5. But I am not able to derive this analytically. My problem is that I am lacking a methodology of handling the $n$ both as a summation limit and a variable in the equation.

$\endgroup$
4
  • $\begingroup$ According to Wolfram alpha this limit is 1 wolframalpha.com/input? $\endgroup$
    – Adi Dani
    Dec 31, 2012 at 20:04
  • 1
    $\begingroup$ Naively (I have not taken analysis or anything like that), I would say this should be 1 as the sum between parentheses goes to $e^n$ as $n\to\infty$. It might be that it converges extremely slowly, which I can imagine, because the higher order terms (which are already in $e^{-n}$) become significant when the argument gets big. $\endgroup$
    – user50407
    Dec 31, 2012 at 20:06
  • $\begingroup$ Sorry for the extra comment, after trying some stuff out numerically I also suspect it goes to $\frac{1}{2}$. I suppose you had already noted what I had said in my previous comment. Sorry that I couldn't help. $\endgroup$
    – user50407
    Dec 31, 2012 at 20:15
  • 2
    $\begingroup$ @mr.FS It is easy to see that the largest term of the infinite series $\sum_i n^i/i!$ occurs at $i=n$, which is exactly where the sum is cut off. Since we're cutting everything from one side of the peak, it's not entirely shocking that we get $\tfrac12$. $\endgroup$
    – Erick Wong
    Dec 31, 2012 at 20:17

2 Answers 2

Reset to default
6
$\begingroup$

I don't want to put this down as my own solution, since I have already seen it solved on MSE.

One way is to use the sum of Poisson RVs with parameter 1, so that $S_n=\sum_{k=1}^{n}X_k, \ S_n \sim Poisson(n)$ and then apply Central Limit Theorem to obtain $\Phi(0)=\frac{1}{2}$.

The other solution is purely analytic and is detailed in the paper by Laszlo and Voros(1999) called 'On the Limit of a Sequence'.

$\endgroup$
3
  • 4
    $\begingroup$ I have to imagine that if an MSE user posted the question "On the Limit of a Sequence", the first comment would be "Please try to use a more descriptive title". $\endgroup$
    – Austin Mohr
    Dec 31, 2012 at 20:16
  • 1
    $\begingroup$ Thanks - just got the paper by Laszlo and Voros. Think this answers my question: link $\endgroup$
    – Klaus Thul
    Dec 31, 2012 at 20:40
  • 1
    $\begingroup$ You are welcome $\endgroup$
    – Alex
    Dec 31, 2012 at 20:40
1
$\begingroup$

Well, we can just get rid of $e^{-n}$ rather easily, but that's not what we should do.

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

There's something called the Incomplete Gamma Function. It satisfies:

$$ \frac{\Gamma(n+1, n)}{n! e^{-n}} = \sum_{k=0}^n \frac{n^k}{k!}$$

Substitute:

$$ \lim_{n\rightarrow\infty} e^{-n} \frac{\Gamma(n+1, n)}{n! e^{-n}} $$

Get rid of $e^{-n}$: $$ \lim_{n\rightarrow\infty} \frac{\Gamma(n+1, n)}{n!} $$

Now what? Well make a substitution: $$ \lim_{n\rightarrow\infty} \frac{\Gamma(n+1, n)}{\Gamma(n+1)} = \frac{1}{2}$$

(Note that the following proof might be incorrect, although my CAS agrees with the result and I think it is.)

In order to show this, there is an identity that $\Gamma(a, x) + \gamma(a, x) = \Gamma(a) $, so $\Gamma(a, x) = \Gamma(a) - \gamma(a, x)$. Now find: $$ \lim_{n\rightarrow\infty} \frac{\Gamma(n+1) - \Gamma(n+1,x)}{\Gamma(n+1)} $$

$$ 1 - \lim_{n\rightarrow\infty} \frac{\Gamma(n+1,x)}{\Gamma(n+1)} $$

But this is the same as our other limit. If we have: $$ \lim_{n\rightarrow\infty} \frac{\Gamma(n+1,x)}{\Gamma(n+1)} = L $$

Then: $$ 1 - L = L $$

So: $$ 1 = 2L $$ $$ \frac{1}{2} = L $$

$\endgroup$
2
  • $\begingroup$ Could you elaborate on that last limit? $\endgroup$
    – WimC
    Dec 31, 2012 at 20:28
  • $\begingroup$ @WimC I can try, although I'm not entirely sure if my reasoning is entirely correct. My CAS seems to agree though. $\endgroup$
    – George V. Williams
    Dec 31, 2012 at 20:37

Not the answer you're looking for? Browse other questions tagged .