Evaluating $limlimits_{ntoinfty} e^{-n} sumlimits_{k=0}^{n} frac{n^k}{k!}$
$begingroup$
I'm supposed to calculate:
$$lim_{ntoinfty} e^{-n} sum_{k=0}^{n} frac{n^k}{k!}$$
By using W|A, i may guess that the limit is $frac{1}{2}$ that is a pretty interesting and nice result. I wonder in which ways we may approach it.
calculus real-analysis sequences-and-series limits
edited May 24 '16 at 19:46
Did
248k23224462
asked Jun 19 '12 at 9:38
user 1357113user 1357113
22.4k877227
$endgroup$
add a comment |
$begingroup$
I'm supposed to calculate:
$$lim_{ntoinfty} e^{-n} sum_{k=0}^{n} frac{n^k}{k!}$$
By using W|A, i may guess that the limit is $frac{1}{2}$ that is a pretty interesting and nice result. I wonder in which ways we may approach it.
calculus real-analysis sequences-and-series limits
edited May 24 '16 at 19:46
Did
248k23224462
asked Jun 19 '12 at 9:38
user 1357113user 1357113
22.4k877227
$endgroup$
4
$begingroup$
Related: math.stackexchange.com/questions/121099/…
$endgroup$
– leonbloy
Jun 19 '12 at 15:46
$begingroup$
This question was merged into the present one.
$endgroup$
– user642796
Oct 1 '13 at 17:16
$begingroup$
[Older question, perhaps merge...] possible duplicate of Partial sums of exponential series
$endgroup$
– Aryabhata
Jan 23 '15 at 17:46
$begingroup$
Also known as Dobiński's formula
$endgroup$
– Machinato
Jun 14 '17 at 13:08
1
$begingroup$
What is W|A , in the question. It says "by using W|A".
$endgroup$
– john
Oct 28 '18 at 10:35
add a comment |
$begingroup$
I'm supposed to calculate:
$$lim_{ntoinfty} e^{-n} sum_{k=0}^{n} frac{n^k}{k!}$$
By using W|A, i may guess that the limit is $frac{1}{2}$ that is a pretty interesting and nice result. I wonder in which ways we may approach it.
calculus real-analysis sequences-and-series limits
edited May 24 '16 at 19:46
Did
248k23224462
asked Jun 19 '12 at 9:38
user 1357113user 1357113
22.4k877227
$endgroup$
I'm supposed to calculate:
$$lim_{ntoinfty} e^{-n} sum_{k=0}^{n} frac{n^k}{k!}$$
By using W|A, i may guess that the limit is $frac{1}{2}$ that is a pretty interesting and nice result. I wonder in which ways we may approach it.
calculus real-analysis sequences-and-series limits
calculus real-analysis sequences-and-series limits
edited May 24 '16 at 19:46
Did
248k23224462
asked Jun 19 '12 at 9:38
user 1357113user 1357113
22.4k877227
edited May 24 '16 at 19:46
Did
248k23224462
asked Jun 19 '12 at 9:38
user 1357113user 1357113
22.4k877227
edited May 24 '16 at 19:46
Did
248k23224462
edited May 24 '16 at 19:46
Did
248k23224462
edited May 24 '16 at 19:46
Did
248k23224462
248k23224462
asked Jun 19 '12 at 9:38
user 1357113user 1357113
22.4k877227
asked Jun 19 '12 at 9:38
user 1357113user 1357113
22.4k877227
asked Jun 19 '12 at 9:38
user 1357113user 1357113
22.4k877227
22.4k877227
4
$begingroup$
Related: math.stackexchange.com/questions/121099/…
$endgroup$
– leonbloy
Jun 19 '12 at 15:46
$begingroup$
This question was merged into the present one.
$endgroup$
– user642796
Oct 1 '13 at 17:16
$begingroup$
[Older question, perhaps merge...] possible duplicate of Partial sums of exponential series
$endgroup$
– Aryabhata
Jan 23 '15 at 17:46
$begingroup$
Also known as Dobiński's formula
$endgroup$
– Machinato
Jun 14 '17 at 13:08
1
$begingroup$
What is W|A , in the question. It says "by using W|A".
$endgroup$
– john
Oct 28 '18 at 10:35
add a comment |
4
$begingroup$
Related: math.stackexchange.com/questions/121099/…
$endgroup$
– leonbloy
Jun 19 '12 at 15:46
$begingroup$
This question was merged into the present one.
$endgroup$
– user642796
Oct 1 '13 at 17:16
$begingroup$
[Older question, perhaps merge...] possible duplicate of Partial sums of exponential series
$endgroup$
– Aryabhata
Jan 23 '15 at 17:46
$begingroup$
Also known as Dobiński's formula
$endgroup$
– Machinato
Jun 14 '17 at 13:08
1
$begingroup$
What is W|A , in the question. It says "by using W|A".
$endgroup$
– john
Oct 28 '18 at 10:35
4
4
$begingroup$
Related: math.stackexchange.com/questions/121099/…
$endgroup$
– leonbloy
Jun 19 '12 at 15:46
$begingroup$
Related: math.stackexchange.com/questions/121099/…
$endgroup$
– leonbloy
Jun 19 '12 at 15:46
$begingroup$
This question was merged into the present one.
$endgroup$
– user642796
Oct 1 '13 at 17:16
$begingroup$
This question was merged into the present one.
$endgroup$
– user642796
Oct 1 '13 at 17:16
$begingroup$
[Older question, perhaps merge...] possible duplicate of Partial sums of exponential series
$endgroup$
– Aryabhata
Jan 23 '15 at 17:46
$begingroup$
[Older question, perhaps merge...] possible duplicate of Partial sums of exponential series
$endgroup$
– Aryabhata
Jan 23 '15 at 17:46
$begingroup$
Also known as Dobiński's formula
$endgroup$
– Machinato
Jun 14 '17 at 13:08
$begingroup$
Also known as Dobiński's formula
$endgroup$
– Machinato
Jun 14 '17 at 13:08
1
1
$begingroup$
What is W|A , in the question. It says "by using W|A".
$endgroup$
– john
Oct 28 '18 at 10:35
$begingroup$
What is W|A , in the question. It says "by using W|A".
$endgroup$
– john
Oct 28 '18 at 10:35
add a comment |
9 Answers
9
active
oldest
votes
$begingroup$
Edited. I justified the application of the dominated convergence theorem.
By a simple calculation,
$$ begin{align*}
e^{-n}sum_{k=0}^{n} frac{n^k}{k!}
&= frac{e^{-n}}{n!} sum_{k=0}^{n}binom{n}{k} n^k (n-k)! \
(1) cdots quad &= frac{e^{-n}}{n!} sum_{k=0}^{n}binom{n}{k} n^k int_{0}^{infty} t^{n-k}e^{-t} , dt\
&= frac{e^{-n}}{n!} int_{0}^{infty} (n+t)^{n}e^{-t} , dt \
(2) cdots quad &= frac{1}{n!} int_{n}^{infty} t^{n}e^{-t} , dt \
&= 1 - frac{1}{n!} int_{0}^{n} t^{n}e^{-t} , dt \
(3) cdots quad &= 1 - frac{sqrt{n} (n/e)^n}{n!} int_{0}^{sqrt{n}} left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} , du.
end{align*}$$
We remark that
- In $text{(1)}$, we utilized the famous formula $ n! = int_{0}^{infty} t^n e^{-t} , dt$.
- In $text{(2)}$, the substitution $t + n mapsto t$ is used.
- In $text{(3)}$, the substitution $t = n - sqrt{n}u$ is used.
Then in view of the Stirling's formula, it suffices to show that
$$int_{0}^{sqrt{n}} left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} , du xrightarrow{ntoinfty} sqrt{frac{pi}{2}}.$$
The idea is to introduce the function
$$ g_n (u) = left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} mathbf{1}_{(0, sqrt{n})}(u) $$
and apply pointwise limit to the integrand as $n to infty$. This is justified once we find a dominating function for the sequence $(g_n)$. But notice that if $0 < u < sqrt{n}$, then
$$ log g_n (u)
= n log left(1 - frac{u}{sqrt{n}} right) + sqrt{n} u
= -frac{u^2}{2} - frac{u^3}{3sqrt{n}} - frac{u^4}{4n} - cdots leq -frac{u^2}{2}. $$
From this we have $g_n (u) leq e^{-u^2 /2}$ for all $n$ and $g_n (u) to e^{-u^2 / 2}$ as $n to infty$. Therefore by dominated convergence theorem and Gaussian integral,
$$ int_{0}^{sqrt{n}} left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} , du = int_{0}^{infty} g_n (u) , du xrightarrow{ntoinfty} int_{0}^{infty} e^{-u^2/2} , du = sqrt{frac{pi}{2}}. $$
answered Jun 19 '12 at 11:27
Sangchul LeeSangchul Lee
93.6k12167271
$endgroup$
2
$begingroup$
Your second equation is closely related to this question (which I answered).
$endgroup$
– robjohn♦
Jun 19 '12 at 15:47
add a comment |
$begingroup$
The probabilistic way:
This is $P[N_nleqslant n]$ where $N_n$ is a random variable with Poisson distribution of parameter $n$. Hence each $N_n$ is distributed like $X_1+cdots+X_n$ where the random variables $(X_k)$ are independent and identically distributed with Poisson distribution of parameter $1$.
By the central limit theorem, $Y_n=frac1{sqrt{n}}(X_1+cdots+X_n-n)$ converges in distribution to a standard normal random variable $Z$, in particular, $P[Y_nleqslant 0]to P[Zleqslant0]$.
Finally, $P[Zleqslant0]=frac12$ and $[N_nleqslant n]=[Y_nleqslant 0]$ hence $P[N_nleqslant n]tofrac12$, QED.
The analytical way, completing your try:
Hence, I know that what I need to do is to find $limlimits_{ntoinfty}I_n$, where
$$
I_n=frac{e^{-n}}{n!}int_{0}^n (n-t)^ne^tdt.$$
To begin with, let $u(t)=(1-t)e^t$, then $I_n=dfrac{e^{-n}n^n}{n!}nJ_n$ with
$$
J_n=int_{0}^1 u(t)^nmathrm dt.
$$
Now, $u(t)leqslantmathrm e^{-t^2/2}$ hence
$$
J_nleqslantint_0^1mathrm e^{-nt^2/2}mathrm dtleqslantint_0^inftymathrm e^{-nt^2/2}mathrm dt=sqrt{frac{pi}{2n}}.
$$
Likewise, the function $tmapsto u(t)mathrm e^{t^2/2}$ is decreasing on $tgeqslant0$ hence $u(t)geqslant c_nmathrm e^{-t^2/2}$ on $tleqslant1/n^{1/4}$, with $c_n=u(1/n^{1/4})mathrm e^{-1/(2sqrt{n})}$, hence
$$
J_ngeqslant c_nint_0^{1/n^{1/4}}mathrm e^{-nt^2/2}mathrm dt=frac{c_n}{sqrt{n}}int_0^{n^{1/4}}mathrm e^{-t^2/2}mathrm dt=frac{c_n}{sqrt{n}}sqrt{frac{pi}{2}}(1+o(1)).
$$
Since $c_nto1$, all this proves that $sqrt{n}J_ntosqrt{fracpi2}$. Stirling formula shows that the prefactor $frac{e^{-n}n^n}{n!}$ is equivalent to $frac1{sqrt{2pi n}}$. Regrouping everything, one sees that $I_nsimfrac1{sqrt{2pi n}}nsqrt{fracpi{2n}}=frac12$.
Moral:
The probabilistic way is shorter, easier, more illuminating, and more fun.
Caveat:
My advice in these matters is, clearly, horribly biased.
answered Sep 14 '13 at 15:40
DidDid
248k23224462
$endgroup$
add a comment |
$begingroup$
Integration by parts yields
$$
frac{1}{k!}int_x^infty e^{-t},t^k,mathrm{d}t=frac{1}{k!}x^ke^{-x}+frac{1}{(k-1)!}int_x^infty e^{-t},t^{k-1},mathrm{d}ttag{1}
$$
Iterating $(1)$ gives
$$
frac{1}{n!}int_x^infty e^{-t},t^n,mathrm{d}t=e^{-x}sum_{k=0}^nfrac{x^k}{k!}tag{2}
$$
Thus, we get
$$
e^{-n}sum_{k=0}^nfrac{n^k}{k!}=frac{1}{n!}int_n^infty e^{-t},t^n,mathrm{d}ttag{3}
$$
Now, I will reproduce part of the argument I give here, which develops a full asymptotic expansion. Additionally, I include some error estimates that were previously missing.
$$
begin{align}
int_n^infty e^{-t},t^n,mathrm{d}t
&=n^{n+1}e^{-n}int_0^infty e^{-ns},(s+1)^n,mathrm{d}s\
&=n^{n+1}e^{-n}int_0^infty e^{-n(s-log(1+s)},mathrm{d}s\
&=n^{n+1}e^{-n}int_0^infty e^{-nu^2/2},s',mathrm{d}utag{4}
end{align}
$$
where $t=n(s+1)$ and $u^2/2=s-log(1+s)$.
Note that $frac{ss'}{1+s}=u$; thus, when $sge1$, $s'le2u$. This leads to the bound
$$
begin{align}
int_{sge1} e^{-nu^2/2},s',mathrm{d}u
&leint_{3/4}^infty e^{-nu^2/2},2u,mathrm{d}u\
&=frac2ne^{-frac98n}tag{5}
end{align}
$$
$(5)$ also show that
$$
int_{sge1}e^{-nu^2/2},mathrm{d}ulefrac2ne^{-frac98n}tag{6}
$$
For $|s|<1$, we get
$$
u^2/2=s-log(1+s)=s^2/2-s^3/3+s^4/4-dotstag{7}
$$
We can invert the series to get $s'=1+frac23u+O(u^2)$. Therefore,
$$
begin{align}
int_0^infty e^{-nu^2/2},s',mathrm{d}u
&=int_{sin[0,1]} e^{-nu^2/2},s',mathrm{d}u+color{red}{int_{s>1} e^{-nu^2/2},s',mathrm{d}u}\
&=int_0^inftyleft(1+frac23uright)e^{-nu^2/2},mathrm{d}u-color{darkorange}{int_{s>1}left(1+frac23uright)e^{-nu^2/2},mathrm{d}u}\
&+int_0^infty e^{-nu^2/2},O(u^2),mathrm{d}u-color{darkorange}{int_{s>1} e^{-nu^2/2},O(u^2),mathrm{d}u}\
&+color{red}{int_{s>1} e^{-nu^2/2},s',mathrm{d}u}\
&=sqrt{frac{pi}{2n}}+frac2{3n}+Oleft(n^{-3/2}right)tag{8}
end{align}
$$
The red and orange integrals decrease exponentially by $(5)$ and $(6)$.
Plugging $(8)$ into $(4)$ yields
$$
int_n^infty e^{-t},t^n,mathrm{d}t=left(sqrt{frac{pi n}{2}}+frac23right),n^ne^{-n}+O(n^{n-1/2}e^{-n})tag{9}
$$
The argument above can be used to prove Stirling's approximation, which says that
$$
n!=sqrt{2pi n},n^ne^{-n}+O(n^{n-1/2}e^{-n})tag{10}
$$
Combining $(9)$ and $(10)$ yields
$$
begin{align}
e^{-n}sum_{k=0}^nfrac{n^k}{k!}
&=frac{1}{n!}int_n^infty e^{-t},t^n,mathrm{d}t\
&=frac12+frac{2/3}{sqrt{2pi n}}+O(n^{-1})tag{11}
end{align}
$$
answered Jun 19 '12 at 15:29
robjohn♦robjohn
268k27308632
$endgroup$
1
$begingroup$
Would the downvoter care to comment (he asked, expecting the answer "no")?
$endgroup$
– robjohn♦
May 12 '18 at 14:01
$begingroup$
hey rob, sadly the link in your answer is dead :(
$endgroup$
– tired
Jun 10 '18 at 14:17
$begingroup$
Yeah too many downvoters here :/ I upvoted this. Very Nice answer.
$endgroup$
– mick
Jun 29 '18 at 21:49
add a comment |
$begingroup$
If you'd like to see formal solution using calculus methods check this article http://www.emis.de/journals/AMAPN/vol15/voros.pdf
answered Jun 19 '12 at 11:09
qoqoszqoqosz
2,7571324
$endgroup$
3
$begingroup$
I wish you had copied the article here. It seemed small enough. References have a habit of pointing to NULL over time.
$endgroup$
– steven gregory
Aug 22 '15 at 5:18
add a comment |
$begingroup$
The sum is related to the partial exponential sum, and thus to the incomplete gamma function,
$$begin{eqnarray*}
e^{-n} sum_{k=0}^{n} frac{n^k}{k!}
&=& e^{-n} e_n(n) \
&=& frac{Gamma(n+1,n)}{Gamma(n+1)},
end{eqnarray*}$$
since $e_n(x) = sum_{k=0}^n x^k/k! = e^x Gamma(n+1,x)/Gamma(n+1)$.
But
$$begin{eqnarray*}
Gamma(n+1,n) &=& sqrt{2pi}, n^{n+1/2}e^{-n}left(frac{1}{2} + frac{1}{3}sqrt{frac{2}{npi}} + Oleft(frac{1}{n}right) right).
end{eqnarray*}$$
The first term in the asymptotic expansion for $Gamma(n+1,n)$ can be found by applying the saddle point method to
$$Gamma(n+1,n) = int_n^infty dt, t^n e^{-t}.$$
The higher order terms are in principle straightforward to compute.
Using Stirling's approximation, we find
$$e^{-n} sum_{k=0}^{n} frac{n^k}{k!}
= frac{1}{2}
+ frac{1}{3}sqrt{frac{2}{npi}}
+ Oleft(frac{1}{n}right).$$
Thus, the limit is $1/2$, as found by @sos440 and @robjohn.
This limit is a special case of DLMF 8.11.13.
I just noticed a comment that suggests this be done using high school level math.
If this is a standard exercise at your high school, maybe they covered the incomplete gamma function! ;-)
answered Jun 20 '12 at 0:22
user26872user26872
14.9k22773
$endgroup$
2
$begingroup$
(+1) I derived this asymptotic expansion here in answer to a question on sci.math. I computed a few terms past $frac12$: $$ frac12+frac{1}{sqrt{2pi n}}left(frac23-frac{23}{270n}+frac{23}{3024n^2}+dotsright) $$
$endgroup$
– robjohn♦
Jun 20 '12 at 3:14
$begingroup$
@robjohn: Thanks for the link, I'll have a look. By the way, I voted up your nice solution a couple of hours ago. I like your short and sweet derivation of (3).
$endgroup$
– user26872
Jun 20 '12 at 3:47
$begingroup$
@robjohn As steven gregory says above "I wish you had copied the article here. It seemed small enough. References have a habit of pointing to NULL over time" . Please, could you upload somewhere again? I'm curious about it.
$endgroup$
– vesszabo
Jul 4 '17 at 21:13
add a comment |
$begingroup$
$newcommand{+}{^{dagger}}
newcommand{angles}[1]{leftlangle #1 rightrangle}
newcommand{braces}[1]{leftlbrace #1 rightrbrace}
newcommand{bracks}[1]{leftlbrack #1 rightrbrack}
newcommand{dd}{{rm d}}
newcommand{isdiv}{,left.rightvert,}
newcommand{ds}[1]{displaystyle{#1}}
newcommand{equalby}[1]{{#1 atop {= atop vphantom{huge A}}}}
newcommand{expo}[1]{,{rm e}^{#1},}
newcommand{floor}[1]{,leftlfloor #1 rightrfloor,}
newcommand{half}{{1 over 2}}
newcommand{ic}{{rm i}}
newcommand{imp}{Longrightarrow}
newcommand{ket}[1]{leftvert #1rightrangle}
newcommand{pars}[1]{left( #1 right)}
newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
newcommand{pp}{{cal P}}
newcommand{root}[2]{,sqrt[#1]{,#2,},}
newcommand{sech}{,{rm sech}}
newcommand{sgn}{,{rm sgn}}
newcommand{totald}[3]{frac{{rm d}^{#1} #2}{{rm d} #3^{#1}}}
newcommand{ul}[1]{underline{#1}}
newcommand{verts}[1]{leftvert #1 rightvert}
newcommand{yy}{Longleftrightarrow}$
begin{align}&color{#00f}{
lim_{n to infty}bracks{expo{-n}sum_{k = 0}^{n}{n^{k} over k!}}}
\[3mm]&=lim_{n to infty}bracks{expo{-n}sum_{k = 0}^{n}
exppars{klnpars{n} - lnpars{k!}}}
\[3mm]&=
lim_{n to infty}braces{expo{-n}sum_{k = 0}^{n}
exppars{nlnpars{n} - lnpars{n!} - {1 over 2n}bracks{k - n}^{2}}}
\[3mm]&=
lim_{n to infty}braces{expo{-n},{n^{n} over n!}sum_{k = 0}^{n}
exppars{-{1 over 2n}bracks{k - n}^{2}}}
\[3mm]&=
lim_{n to infty}braces{{expo{-n}n^{n} over n!}int_{0}^{n}
exppars{-{1 over 2n}bracks{k - n}^{2}},dd k}
\[3mm]&=
lim_{n to infty}bracks{{expo{-n}n^{n} over n!}int_{-n}^{0}
exppars{-,{k^{2} over 2n}},dd k}
=
lim_{n to infty}bracks{{expo{-n}n^{n} over n!},root{2n}
int_{-root{n}/2}^{0}exppars{-k^{2}},dd k}
\[3mm]&=
lim_{n to infty}bracks{{root{2}n^{n + 1/2}expo{-n} over n!}
int_{-infty}^{0}exppars{-k^{2}},dd k}
=
lim_{n to infty}bracks{{root{2}n^{n + 1/2}expo{-n} over n!}
,{root{pi} over 2}}
\[3mm]&=
half,lim_{n to infty}bracks{{root{2pi}n^{n + 1/2}expo{-n} over n!}}
=color{#00f}{Largehalf}
end{align}
edited May 25 '15 at 4:02
Lucian
41.2k159130
answered Nov 12 '13 at 15:20
Felix MarinFelix Marin
68k7107142
$endgroup$
15
$begingroup$
The second equal sign is a complete mystery. The passage from a sum to an integral also needs justification but it probably holds.
$endgroup$
– Did
Mar 31 '14 at 16:25
9
$begingroup$
Would you care answering @Did 's question regarding the second equal sign? I am miffed as well. Thank you, Felix Marin.
$endgroup$
– Hans
May 11 '15 at 17:35
4
$begingroup$
@Did's question has to be answered otherwise this seems to be an suitable answer
$endgroup$
– tired
Oct 4 '15 at 12:12
3
$begingroup$
yeah for me too, can you please answer @Did 's question?
$endgroup$
– user153330
Mar 1 '16 at 20:40
1
$begingroup$
Is this supposed to justify the various unsubstantiated claims this post relies on? It does not.
$endgroup$
– Did
Feb 8 '18 at 17:56
|
show 2 more comments
$begingroup$
I'll give you two hints:
1) Poisson distributions;
2) Central limit theorem
I am not aware of any other technique to solve the problem, so any other answer is appreciated.
edited Jun 19 '12 at 10:53
DonAntonio
178k1494230
answered Jun 19 '12 at 9:50
D. ThomineD. Thomine
7,5691538
$endgroup$
3
$begingroup$
In what country's education system is this a high school exercise?! I ask sincerely because I'm interested in that, and my experience is that even some of the most advanced mathematically education systems don't reach exercises as the one you're proposing...not even close. Of course, I don't know all the education systems (not even close, again), but the expression within the sum seems to be pretty tough...it reminds the series for the exponential function, but that n repeating in the numerator and upper limit...are you sure the expression is accurate?
$endgroup$
– DonAntonio
Jun 19 '12 at 10:17
2
$begingroup$
This problem is definitely not at high-school level. Without the hints I gave, I doubt most university students (even graduates) would solve it in reasonable time.
$endgroup$
– D. Thomine
Jun 19 '12 at 10:43
$begingroup$
The solution using Poisson distribution was also given here: Limit using Poisson distribution
$endgroup$
– Martin Sleziak
Jun 19 '12 at 15:44
$begingroup$
We actually made this exercice in our probability course.
$endgroup$
– Math_QED
Nov 26 '18 at 10:09
add a comment |
$begingroup$
I do not know how much this will help you.
For a given $n$, the result is $dfrac{Gamma(n+1,n)}{n Gamma(n)}$ which has a limit equal to $dfrac12$ as $ntoinfty$.
edited May 18 '14 at 10:54
Tunk-Fey
23.1k970100
answered Sep 14 '13 at 14:33
Claude LeiboviciClaude Leibovici
121k1157133
$endgroup$
add a comment |
$begingroup$
On this page there is a nice collection of evidence.
I add another proof which also uses the Stirling formula.
$displaystyle e^{-n}sumlimits_{k=0}^nfrac{n^k}{k!} = e^{-n}sumlimits_{k=0}^nfrac{k^k (n-k)^{n-k}}{k!(n-k)!} hspace{4cm}$ e.g. here
$displaystyle = limlimits_{ntoinfty} e^{-n}sumlimits_{k=1}^{n-1}frac{e^k e^{n-k}}{sqrt{2pi k (1+mathcal{O}(1/k))}sqrt{2pi (n-k)(1+mathcal{O}(1/(n-k)))}} $
$displaystyle = limlimits_{ntoinfty} frac{1}{2pi}frac{1}{n}sumlimits_{k=1}^{n-1}frac{1}{sqrt{frac{k}{n}left(1-frac{k}{n}right)}} =frac{1}{2pi} intlimits_0^1frac{dx}{sqrt{x(1-x)}}=frac{Gamma(frac{1}{2})^2}{2pi~Gamma(1)} = frac{1}{2}$
answered Nov 26 '18 at 9:54
user90369user90369
8,188925
$endgroup$
$begingroup$
(+1) Interesting idea.
$endgroup$
– user 1357113
Nov 26 '18 at 22:23
$begingroup$
@user1357113 : That's kind of you, thanks. :)
$endgroup$
– user90369
Nov 27 '18 at 8:09
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f160248%2fevaluating-lim-limits-n-to-infty-e-n-sum-limits-k-0n-fracnkk%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
9 Answers
9
active
oldest
votes
9 Answers
9
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Edited. I justified the application of the dominated convergence theorem.
By a simple calculation,
$$ begin{align*}
e^{-n}sum_{k=0}^{n} frac{n^k}{k!}
&= frac{e^{-n}}{n!} sum_{k=0}^{n}binom{n}{k} n^k (n-k)! \
(1) cdots quad &= frac{e^{-n}}{n!} sum_{k=0}^{n}binom{n}{k} n^k int_{0}^{infty} t^{n-k}e^{-t} , dt\
&= frac{e^{-n}}{n!} int_{0}^{infty} (n+t)^{n}e^{-t} , dt \
(2) cdots quad &= frac{1}{n!} int_{n}^{infty} t^{n}e^{-t} , dt \
&= 1 - frac{1}{n!} int_{0}^{n} t^{n}e^{-t} , dt \
(3) cdots quad &= 1 - frac{sqrt{n} (n/e)^n}{n!} int_{0}^{sqrt{n}} left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} , du.
end{align*}$$
We remark that
- In $text{(1)}$, we utilized the famous formula $ n! = int_{0}^{infty} t^n e^{-t} , dt$.
- In $text{(2)}$, the substitution $t + n mapsto t$ is used.
- In $text{(3)}$, the substitution $t = n - sqrt{n}u$ is used.
Then in view of the Stirling's formula, it suffices to show that
$$int_{0}^{sqrt{n}} left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} , du xrightarrow{ntoinfty} sqrt{frac{pi}{2}}.$$
The idea is to introduce the function
$$ g_n (u) = left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} mathbf{1}_{(0, sqrt{n})}(u) $$
and apply pointwise limit to the integrand as $n to infty$. This is justified once we find a dominating function for the sequence $(g_n)$. But notice that if $0 < u < sqrt{n}$, then
$$ log g_n (u)
= n log left(1 - frac{u}{sqrt{n}} right) + sqrt{n} u
= -frac{u^2}{2} - frac{u^3}{3sqrt{n}} - frac{u^4}{4n} - cdots leq -frac{u^2}{2}. $$
From this we have $g_n (u) leq e^{-u^2 /2}$ for all $n$ and $g_n (u) to e^{-u^2 / 2}$ as $n to infty$. Therefore by dominated convergence theorem and Gaussian integral,
$$ int_{0}^{sqrt{n}} left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} , du = int_{0}^{infty} g_n (u) , du xrightarrow{ntoinfty} int_{0}^{infty} e^{-u^2/2} , du = sqrt{frac{pi}{2}}. $$
answered Jun 19 '12 at 11:27
Sangchul LeeSangchul Lee
93.6k12167271
$endgroup$
2
$begingroup$
Your second equation is closely related to this question (which I answered).
$endgroup$
– robjohn♦
Jun 19 '12 at 15:47
add a comment |
$begingroup$
Edited. I justified the application of the dominated convergence theorem.
By a simple calculation,
$$ begin{align*}
e^{-n}sum_{k=0}^{n} frac{n^k}{k!}
&= frac{e^{-n}}{n!} sum_{k=0}^{n}binom{n}{k} n^k (n-k)! \
(1) cdots quad &= frac{e^{-n}}{n!} sum_{k=0}^{n}binom{n}{k} n^k int_{0}^{infty} t^{n-k}e^{-t} , dt\
&= frac{e^{-n}}{n!} int_{0}^{infty} (n+t)^{n}e^{-t} , dt \
(2) cdots quad &= frac{1}{n!} int_{n}^{infty} t^{n}e^{-t} , dt \
&= 1 - frac{1}{n!} int_{0}^{n} t^{n}e^{-t} , dt \
(3) cdots quad &= 1 - frac{sqrt{n} (n/e)^n}{n!} int_{0}^{sqrt{n}} left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} , du.
end{align*}$$
We remark that
- In $text{(1)}$, we utilized the famous formula $ n! = int_{0}^{infty} t^n e^{-t} , dt$.
- In $text{(2)}$, the substitution $t + n mapsto t$ is used.
- In $text{(3)}$, the substitution $t = n - sqrt{n}u$ is used.
Then in view of the Stirling's formula, it suffices to show that
$$int_{0}^{sqrt{n}} left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} , du xrightarrow{ntoinfty} sqrt{frac{pi}{2}}.$$
The idea is to introduce the function
$$ g_n (u) = left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} mathbf{1}_{(0, sqrt{n})}(u) $$
and apply pointwise limit to the integrand as $n to infty$. This is justified once we find a dominating function for the sequence $(g_n)$. But notice that if $0 < u < sqrt{n}$, then
$$ log g_n (u)
= n log left(1 - frac{u}{sqrt{n}} right) + sqrt{n} u
= -frac{u^2}{2} - frac{u^3}{3sqrt{n}} - frac{u^4}{4n} - cdots leq -frac{u^2}{2}. $$
From this we have $g_n (u) leq e^{-u^2 /2}$ for all $n$ and $g_n (u) to e^{-u^2 / 2}$ as $n to infty$. Therefore by dominated convergence theorem and Gaussian integral,
$$ int_{0}^{sqrt{n}} left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} , du = int_{0}^{infty} g_n (u) , du xrightarrow{ntoinfty} int_{0}^{infty} e^{-u^2/2} , du = sqrt{frac{pi}{2}}. $$
answered Jun 19 '12 at 11:27
Sangchul LeeSangchul Lee
93.6k12167271
$endgroup$
2
$begingroup$
Your second equation is closely related to this question (which I answered).
$endgroup$
– robjohn♦
Jun 19 '12 at 15:47
add a comment |
$begingroup$
Edited. I justified the application of the dominated convergence theorem.
By a simple calculation,
$$ begin{align*}
e^{-n}sum_{k=0}^{n} frac{n^k}{k!}
&= frac{e^{-n}}{n!} sum_{k=0}^{n}binom{n}{k} n^k (n-k)! \
(1) cdots quad &= frac{e^{-n}}{n!} sum_{k=0}^{n}binom{n}{k} n^k int_{0}^{infty} t^{n-k}e^{-t} , dt\
&= frac{e^{-n}}{n!} int_{0}^{infty} (n+t)^{n}e^{-t} , dt \
(2) cdots quad &= frac{1}{n!} int_{n}^{infty} t^{n}e^{-t} , dt \
&= 1 - frac{1}{n!} int_{0}^{n} t^{n}e^{-t} , dt \
(3) cdots quad &= 1 - frac{sqrt{n} (n/e)^n}{n!} int_{0}^{sqrt{n}} left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} , du.
end{align*}$$
We remark that
- In $text{(1)}$, we utilized the famous formula $ n! = int_{0}^{infty} t^n e^{-t} , dt$.
- In $text{(2)}$, the substitution $t + n mapsto t$ is used.
- In $text{(3)}$, the substitution $t = n - sqrt{n}u$ is used.
Then in view of the Stirling's formula, it suffices to show that
$$int_{0}^{sqrt{n}} left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} , du xrightarrow{ntoinfty} sqrt{frac{pi}{2}}.$$
The idea is to introduce the function
$$ g_n (u) = left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} mathbf{1}_{(0, sqrt{n})}(u) $$
and apply pointwise limit to the integrand as $n to infty$. This is justified once we find a dominating function for the sequence $(g_n)$. But notice that if $0 < u < sqrt{n}$, then
$$ log g_n (u)
= n log left(1 - frac{u}{sqrt{n}} right) + sqrt{n} u
= -frac{u^2}{2} - frac{u^3}{3sqrt{n}} - frac{u^4}{4n} - cdots leq -frac{u^2}{2}. $$
From this we have $g_n (u) leq e^{-u^2 /2}$ for all $n$ and $g_n (u) to e^{-u^2 / 2}$ as $n to infty$. Therefore by dominated convergence theorem and Gaussian integral,
$$ int_{0}^{sqrt{n}} left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} , du = int_{0}^{infty} g_n (u) , du xrightarrow{ntoinfty} int_{0}^{infty} e^{-u^2/2} , du = sqrt{frac{pi}{2}}. $$
answered Jun 19 '12 at 11:27
Sangchul LeeSangchul Lee
93.6k12167271
$endgroup$
Edited. I justified the application of the dominated convergence theorem.
By a simple calculation,
$$ begin{align*}
e^{-n}sum_{k=0}^{n} frac{n^k}{k!}
&= frac{e^{-n}}{n!} sum_{k=0}^{n}binom{n}{k} n^k (n-k)! \
(1) cdots quad &= frac{e^{-n}}{n!} sum_{k=0}^{n}binom{n}{k} n^k int_{0}^{infty} t^{n-k}e^{-t} , dt\
&= frac{e^{-n}}{n!} int_{0}^{infty} (n+t)^{n}e^{-t} , dt \
(2) cdots quad &= frac{1}{n!} int_{n}^{infty} t^{n}e^{-t} , dt \
&= 1 - frac{1}{n!} int_{0}^{n} t^{n}e^{-t} , dt \
(3) cdots quad &= 1 - frac{sqrt{n} (n/e)^n}{n!} int_{0}^{sqrt{n}} left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} , du.
end{align*}$$
We remark that
- In $text{(1)}$, we utilized the famous formula $ n! = int_{0}^{infty} t^n e^{-t} , dt$.
- In $text{(2)}$, the substitution $t + n mapsto t$ is used.
- In $text{(3)}$, the substitution $t = n - sqrt{n}u$ is used.
Then in view of the Stirling's formula, it suffices to show that
$$int_{0}^{sqrt{n}} left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} , du xrightarrow{ntoinfty} sqrt{frac{pi}{2}}.$$
The idea is to introduce the function
$$ g_n (u) = left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} mathbf{1}_{(0, sqrt{n})}(u) $$
and apply pointwise limit to the integrand as $n to infty$. This is justified once we find a dominating function for the sequence $(g_n)$. But notice that if $0 < u < sqrt{n}$, then
$$ log g_n (u)
= n log left(1 - frac{u}{sqrt{n}} right) + sqrt{n} u
= -frac{u^2}{2} - frac{u^3}{3sqrt{n}} - frac{u^4}{4n} - cdots leq -frac{u^2}{2}. $$
From this we have $g_n (u) leq e^{-u^2 /2}$ for all $n$ and $g_n (u) to e^{-u^2 / 2}$ as $n to infty$. Therefore by dominated convergence theorem and Gaussian integral,
$$ int_{0}^{sqrt{n}} left(1 - frac{u}{sqrt{n}} right)^{n}e^{sqrt{n}u} , du = int_{0}^{infty} g_n (u) , du xrightarrow{ntoinfty} int_{0}^{infty} e^{-u^2/2} , du = sqrt{frac{pi}{2}}. $$
answered Jun 19 '12 at 11:27
Sangchul LeeSangchul Lee
93.6k12167271
edited Jul 30 '15 at 18:22
answered Jun 19 '12 at 11:27
Sangchul LeeSangchul Lee
93.6k12167271
answered Jun 19 '12 at 11:27
Sangchul LeeSangchul Lee
93.6k12167271
answered Jun 19 '12 at 11:27
Sangchul LeeSangchul Lee
93.6k12167271
93.6k12167271
2
$begingroup$
Your second equation is closely related to this question (which I answered).
$endgroup$
– robjohn♦
Jun 19 '12 at 15:47
add a comment |
2
$begingroup$
Your second equation is closely related to this question (which I answered).
$endgroup$
– robjohn♦
Jun 19 '12 at 15:47
2
2
$begingroup$
Your second equation is closely related to this question (which I answered).
$endgroup$
– robjohn♦
Jun 19 '12 at 15:47
$begingroup$
Your second equation is closely related to this question (which I answered).
$endgroup$
– robjohn♦
Jun 19 '12 at 15:47
add a comment |
$begingroup$
The probabilistic way:
This is $P[N_nleqslant n]$ where $N_n$ is a random variable with Poisson distribution of parameter $n$. Hence each $N_n$ is distributed like $X_1+cdots+X_n$ where the random variables $(X_k)$ are independent and identically distributed with Poisson distribution of parameter $1$.
By the central limit theorem, $Y_n=frac1{sqrt{n}}(X_1+cdots+X_n-n)$ converges in distribution to a standard normal random variable $Z$, in particular, $P[Y_nleqslant 0]to P[Zleqslant0]$.
Finally, $P[Zleqslant0]=frac12$ and $[N_nleqslant n]=[Y_nleqslant 0]$ hence $P[N_nleqslant n]tofrac12$, QED.
The analytical way, completing your try:
Hence, I know that what I need to do is to find $limlimits_{ntoinfty}I_n$, where
$$
I_n=frac{e^{-n}}{n!}int_{0}^n (n-t)^ne^tdt.$$
To begin with, let $u(t)=(1-t)e^t$, then $I_n=dfrac{e^{-n}n^n}{n!}nJ_n$ with
$$
J_n=int_{0}^1 u(t)^nmathrm dt.
$$
Now, $u(t)leqslantmathrm e^{-t^2/2}$ hence
$$
J_nleqslantint_0^1mathrm e^{-nt^2/2}mathrm dtleqslantint_0^inftymathrm e^{-nt^2/2}mathrm dt=sqrt{frac{pi}{2n}}.
$$
Likewise, the function $tmapsto u(t)mathrm e^{t^2/2}$ is decreasing on $tgeqslant0$ hence $u(t)geqslant c_nmathrm e^{-t^2/2}$ on $tleqslant1/n^{1/4}$, with $c_n=u(1/n^{1/4})mathrm e^{-1/(2sqrt{n})}$, hence
$$
J_ngeqslant c_nint_0^{1/n^{1/4}}mathrm e^{-nt^2/2}mathrm dt=frac{c_n}{sqrt{n}}int_0^{n^{1/4}}mathrm e^{-t^2/2}mathrm dt=frac{c_n}{sqrt{n}}sqrt{frac{pi}{2}}(1+o(1)).
$$
Since $c_nto1$, all this proves that $sqrt{n}J_ntosqrt{fracpi2}$. Stirling formula shows that the prefactor $frac{e^{-n}n^n}{n!}$ is equivalent to $frac1{sqrt{2pi n}}$. Regrouping everything, one sees that $I_nsimfrac1{sqrt{2pi n}}nsqrt{fracpi{2n}}=frac12$.
Moral:
The probabilistic way is shorter, easier, more illuminating, and more fun.
Caveat:
My advice in these matters is, clearly, horribly biased.
answered Sep 14 '13 at 15:40
DidDid
248k23224462
$endgroup$
add a comment |
$begingroup$
The probabilistic way:
This is $P[N_nleqslant n]$ where $N_n$ is a random variable with Poisson distribution of parameter $n$. Hence each $N_n$ is distributed like $X_1+cdots+X_n$ where the random variables $(X_k)$ are independent and identically distributed with Poisson distribution of parameter $1$.
By the central limit theorem, $Y_n=frac1{sqrt{n}}(X_1+cdots+X_n-n)$ converges in distribution to a standard normal random variable $Z$, in particular, $P[Y_nleqslant 0]to P[Zleqslant0]$.
Finally, $P[Zleqslant0]=frac12$ and $[N_nleqslant n]=[Y_nleqslant 0]$ hence $P[N_nleqslant n]tofrac12$, QED.
The analytical way, completing your try:
Hence, I know that what I need to do is to find $limlimits_{ntoinfty}I_n$, where
$$
I_n=frac{e^{-n}}{n!}int_{0}^n (n-t)^ne^tdt.$$
To begin with, let $u(t)=(1-t)e^t$, then $I_n=dfrac{e^{-n}n^n}{n!}nJ_n$ with
$$
J_n=int_{0}^1 u(t)^nmathrm dt.
$$
Now, $u(t)leqslantmathrm e^{-t^2/2}$ hence
$$
J_nleqslantint_0^1mathrm e^{-nt^2/2}mathrm dtleqslantint_0^inftymathrm e^{-nt^2/2}mathrm dt=sqrt{frac{pi}{2n}}.
$$
Likewise, the function $tmapsto u(t)mathrm e^{t^2/2}$ is decreasing on $tgeqslant0$ hence $u(t)geqslant c_nmathrm e^{-t^2/2}$ on $tleqslant1/n^{1/4}$, with $c_n=u(1/n^{1/4})mathrm e^{-1/(2sqrt{n})}$, hence
$$
J_ngeqslant c_nint_0^{1/n^{1/4}}mathrm e^{-nt^2/2}mathrm dt=frac{c_n}{sqrt{n}}int_0^{n^{1/4}}mathrm e^{-t^2/2}mathrm dt=frac{c_n}{sqrt{n}}sqrt{frac{pi}{2}}(1+o(1)).
$$
Since $c_nto1$, all this proves that $sqrt{n}J_ntosqrt{fracpi2}$. Stirling formula shows that the prefactor $frac{e^{-n}n^n}{n!}$ is equivalent to $frac1{sqrt{2pi n}}$. Regrouping everything, one sees that $I_nsimfrac1{sqrt{2pi n}}nsqrt{fracpi{2n}}=frac12$.
Moral:
The probabilistic way is shorter, easier, more illuminating, and more fun.
Caveat:
My advice in these matters is, clearly, horribly biased.
answered Sep 14 '13 at 15:40
DidDid
248k23224462
$endgroup$
add a comment |
$begingroup$
The probabilistic way:
This is $P[N_nleqslant n]$ where $N_n$ is a random variable with Poisson distribution of parameter $n$. Hence each $N_n$ is distributed like $X_1+cdots+X_n$ where the random variables $(X_k)$ are independent and identically distributed with Poisson distribution of parameter $1$.
By the central limit theorem, $Y_n=frac1{sqrt{n}}(X_1+cdots+X_n-n)$ converges in distribution to a standard normal random variable $Z$, in particular, $P[Y_nleqslant 0]to P[Zleqslant0]$.
Finally, $P[Zleqslant0]=frac12$ and $[N_nleqslant n]=[Y_nleqslant 0]$ hence $P[N_nleqslant n]tofrac12$, QED.
The analytical way, completing your try:
Hence, I know that what I need to do is to find $limlimits_{ntoinfty}I_n$, where
$$
I_n=frac{e^{-n}}{n!}int_{0}^n (n-t)^ne^tdt.$$
To begin with, let $u(t)=(1-t)e^t$, then $I_n=dfrac{e^{-n}n^n}{n!}nJ_n$ with
$$
J_n=int_{0}^1 u(t)^nmathrm dt.
$$
Now, $u(t)leqslantmathrm e^{-t^2/2}$ hence
$$
J_nleqslantint_0^1mathrm e^{-nt^2/2}mathrm dtleqslantint_0^inftymathrm e^{-nt^2/2}mathrm dt=sqrt{frac{pi}{2n}}.
$$
Likewise, the function $tmapsto u(t)mathrm e^{t^2/2}$ is decreasing on $tgeqslant0$ hence $u(t)geqslant c_nmathrm e^{-t^2/2}$ on $tleqslant1/n^{1/4}$, with $c_n=u(1/n^{1/4})mathrm e^{-1/(2sqrt{n})}$, hence
$$
J_ngeqslant c_nint_0^{1/n^{1/4}}mathrm e^{-nt^2/2}mathrm dt=frac{c_n}{sqrt{n}}int_0^{n^{1/4}}mathrm e^{-t^2/2}mathrm dt=frac{c_n}{sqrt{n}}sqrt{frac{pi}{2}}(1+o(1)).
$$
Since $c_nto1$, all this proves that $sqrt{n}J_ntosqrt{fracpi2}$. Stirling formula shows that the prefactor $frac{e^{-n}n^n}{n!}$ is equivalent to $frac1{sqrt{2pi n}}$. Regrouping everything, one sees that $I_nsimfrac1{sqrt{2pi n}}nsqrt{fracpi{2n}}=frac12$.
Moral:
The probabilistic way is shorter, easier, more illuminating, and more fun.
Caveat:
My advice in these matters is, clearly, horribly biased.
answered Sep 14 '13 at 15:40
DidDid
248k23224462
$endgroup$
The probabilistic way:
This is $P[N_nleqslant n]$ where $N_n$ is a random variable with Poisson distribution of parameter $n$. Hence each $N_n$ is distributed like $X_1+cdots+X_n$ where the random variables $(X_k)$ are independent and identically distributed with Poisson distribution of parameter $1$.
By the central limit theorem, $Y_n=frac1{sqrt{n}}(X_1+cdots+X_n-n)$ converges in distribution to a standard normal random variable $Z$, in particular, $P[Y_nleqslant 0]to P[Zleqslant0]$.
Finally, $P[Zleqslant0]=frac12$ and $[N_nleqslant n]=[Y_nleqslant 0]$ hence $P[N_nleqslant n]tofrac12$, QED.
The analytical way, completing your try:
Hence, I know that what I need to do is to find $limlimits_{ntoinfty}I_n$, where
$$
I_n=frac{e^{-n}}{n!}int_{0}^n (n-t)^ne^tdt.$$
To begin with, let $u(t)=(1-t)e^t$, then $I_n=dfrac{e^{-n}n^n}{n!}nJ_n$ with
$$
J_n=int_{0}^1 u(t)^nmathrm dt.
$$
Now, $u(t)leqslantmathrm e^{-t^2/2}$ hence
$$
J_nleqslantint_0^1mathrm e^{-nt^2/2}mathrm dtleqslantint_0^inftymathrm e^{-nt^2/2}mathrm dt=sqrt{frac{pi}{2n}}.
$$
Likewise, the function $tmapsto u(t)mathrm e^{t^2/2}$ is decreasing on $tgeqslant0$ hence $u(t)geqslant c_nmathrm e^{-t^2/2}$ on $tleqslant1/n^{1/4}$, with $c_n=u(1/n^{1/4})mathrm e^{-1/(2sqrt{n})}$, hence
$$
J_ngeqslant c_nint_0^{1/n^{1/4}}mathrm e^{-nt^2/2}mathrm dt=frac{c_n}{sqrt{n}}int_0^{n^{1/4}}mathrm e^{-t^2/2}mathrm dt=frac{c_n}{sqrt{n}}sqrt{frac{pi}{2}}(1+o(1)).
$$
Since $c_nto1$, all this proves that $sqrt{n}J_ntosqrt{fracpi2}$. Stirling formula shows that the prefactor $frac{e^{-n}n^n}{n!}$ is equivalent to $frac1{sqrt{2pi n}}$. Regrouping everything, one sees that $I_nsimfrac1{sqrt{2pi n}}nsqrt{fracpi{2n}}=frac12$.
Moral:
The probabilistic way is shorter, easier, more illuminating, and more fun.
Caveat:
My advice in these matters is, clearly, horribly biased.
answered Sep 14 '13 at 15:40
DidDid
248k23224462
edited Jul 4 '17 at 11:19
answered Sep 14 '13 at 15:40
DidDid
248k23224462
answered Sep 14 '13 at 15:40
DidDid
248k23224462
answered Sep 14 '13 at 15:40
DidDid
248k23224462
248k23224462
add a comment |
add a comment |
$begingroup$
Integration by parts yields
$$
frac{1}{k!}int_x^infty e^{-t},t^k,mathrm{d}t=frac{1}{k!}x^ke^{-x}+frac{1}{(k-1)!}int_x^infty e^{-t},t^{k-1},mathrm{d}ttag{1}
$$
Iterating $(1)$ gives
$$
frac{1}{n!}int_x^infty e^{-t},t^n,mathrm{d}t=e^{-x}sum_{k=0}^nfrac{x^k}{k!}tag{2}
$$
Thus, we get
$$
e^{-n}sum_{k=0}^nfrac{n^k}{k!}=frac{1}{n!}int_n^infty e^{-t},t^n,mathrm{d}ttag{3}
$$
Now, I will reproduce part of the argument I give here, which develops a full asymptotic expansion. Additionally, I include some error estimates that were previously missing.
$$
begin{align}
int_n^infty e^{-t},t^n,mathrm{d}t
&=n^{n+1}e^{-n}int_0^infty e^{-ns},(s+1)^n,mathrm{d}s\
&=n^{n+1}e^{-n}int_0^infty e^{-n(s-log(1+s)},mathrm{d}s\
&=n^{n+1}e^{-n}int_0^infty e^{-nu^2/2},s',mathrm{d}utag{4}
end{align}
$$
where $t=n(s+1)$ and $u^2/2=s-log(1+s)$.
Note that $frac{ss'}{1+s}=u$; thus, when $sge1$, $s'le2u$. This leads to the bound
$$
begin{align}
int_{sge1} e^{-nu^2/2},s',mathrm{d}u
&leint_{3/4}^infty e^{-nu^2/2},2u,mathrm{d}u\
&=frac2ne^{-frac98n}tag{5}
end{align}
$$
$(5)$ also show that
$$
int_{sge1}e^{-nu^2/2},mathrm{d}ulefrac2ne^{-frac98n}tag{6}
$$
For $|s|<1$, we get
$$
u^2/2=s-log(1+s)=s^2/2-s^3/3+s^4/4-dotstag{7}
$$
We can invert the series to get $s'=1+frac23u+O(u^2)$. Therefore,
$$
begin{align}
int_0^infty e^{-nu^2/2},s',mathrm{d}u
&=int_{sin[0,1]} e^{-nu^2/2},s',mathrm{d}u+color{red}{int_{s>1} e^{-nu^2/2},s',mathrm{d}u}\
&=int_0^inftyleft(1+frac23uright)e^{-nu^2/2},mathrm{d}u-color{darkorange}{int_{s>1}left(1+frac23uright)e^{-nu^2/2},mathrm{d}u}\
&+int_0^infty e^{-nu^2/2},O(u^2),mathrm{d}u-color{darkorange}{int_{s>1} e^{-nu^2/2},O(u^2),mathrm{d}u}\
&+color{red}{int_{s>1} e^{-nu^2/2},s',mathrm{d}u}\
&=sqrt{frac{pi}{2n}}+frac2{3n}+Oleft(n^{-3/2}right)tag{8}
end{align}
$$
The red and orange integrals decrease exponentially by $(5)$ and $(6)$.
Plugging $(8)$ into $(4)$ yields
$$
int_n^infty e^{-t},t^n,mathrm{d}t=left(sqrt{frac{pi n}{2}}+frac23right),n^ne^{-n}+O(n^{n-1/2}e^{-n})tag{9}
$$
The argument above can be used to prove Stirling's approximation, which says that
$$
n!=sqrt{2pi n},n^ne^{-n}+O(n^{n-1/2}e^{-n})tag{10}
$$
Combining $(9)$ and $(10)$ yields
$$
begin{align}
e^{-n}sum_{k=0}^nfrac{n^k}{k!}
&=frac{1}{n!}int_n^infty e^{-t},t^n,mathrm{d}t\
&=frac12+frac{2/3}{sqrt{2pi n}}+O(n^{-1})tag{11}
end{align}
$$
answered Jun 19 '12 at 15:29
robjohn♦robjohn
268k27308632
$endgroup$
1
$begingroup$
Would the downvoter care to comment (he asked, expecting the answer "no")?
$endgroup$
– robjohn♦
May 12 '18 at 14:01
$begingroup$
hey rob, sadly the link in your answer is dead :(
$endgroup$
– tired
Jun 10 '18 at 14:17
$begingroup$
Yeah too many downvoters here :/ I upvoted this. Very Nice answer.
$endgroup$
– mick
Jun 29 '18 at 21:49
add a comment |
$begingroup$
Integration by parts yields
$$
frac{1}{k!}int_x^infty e^{-t},t^k,mathrm{d}t=frac{1}{k!}x^ke^{-x}+frac{1}{(k-1)!}int_x^infty e^{-t},t^{k-1},mathrm{d}ttag{1}
$$
Iterating $(1)$ gives
$$
frac{1}{n!}int_x^infty e^{-t},t^n,mathrm{d}t=e^{-x}sum_{k=0}^nfrac{x^k}{k!}tag{2}
$$
Thus, we get
$$
e^{-n}sum_{k=0}^nfrac{n^k}{k!}=frac{1}{n!}int_n^infty e^{-t},t^n,mathrm{d}ttag{3}
$$
Now, I will reproduce part of the argument I give here, which develops a full asymptotic expansion. Additionally, I include some error estimates that were previously missing.
$$
begin{align}
int_n^infty e^{-t},t^n,mathrm{d}t
&=n^{n+1}e^{-n}int_0^infty e^{-ns},(s+1)^n,mathrm{d}s\
&=n^{n+1}e^{-n}int_0^infty e^{-n(s-log(1+s)},mathrm{d}s\
&=n^{n+1}e^{-n}int_0^infty e^{-nu^2/2},s',mathrm{d}utag{4}
end{align}
$$
where $t=n(s+1)$ and $u^2/2=s-log(1+s)$.
Note that $frac{ss'}{1+s}=u$; thus, when $sge1$, $s'le2u$. This leads to the bound
$$
begin{align}
int_{sge1} e^{-nu^2/2},s',mathrm{d}u
&leint_{3/4}^infty e^{-nu^2/2},2u,mathrm{d}u\
&=frac2ne^{-frac98n}tag{5}
end{align}
$$
$(5)$ also show that
$$
int_{sge1}e^{-nu^2/2},mathrm{d}ulefrac2ne^{-frac98n}tag{6}
$$
For $|s|<1$, we get
$$
u^2/2=s-log(1+s)=s^2/2-s^3/3+s^4/4-dotstag{7}
$$
We can invert the series to get $s'=1+frac23u+O(u^2)$. Therefore,
$$
begin{align}
int_0^infty e^{-nu^2/2},s',mathrm{d}u
&=int_{sin[0,1]} e^{-nu^2/2},s',mathrm{d}u+color{red}{int_{s>1} e^{-nu^2/2},s',mathrm{d}u}\
&=int_0^inftyleft(1+frac23uright)e^{-nu^2/2},mathrm{d}u-color{darkorange}{int_{s>1}left(1+frac23uright)e^{-nu^2/2},mathrm{d}u}\
&+int_0^infty e^{-nu^2/2},O(u^2),mathrm{d}u-color{darkorange}{int_{s>1} e^{-nu^2/2},O(u^2),mathrm{d}u}\
&+color{red}{int_{s>1} e^{-nu^2/2},s',mathrm{d}u}\
&=sqrt{frac{pi}{2n}}+frac2{3n}+Oleft(n^{-3/2}right)tag{8}
end{align}
$$
The red and orange integrals decrease exponentially by $(5)$ and $(6)$.
Plugging $(8)$ into $(4)$ yields
$$
int_n^infty e^{-t},t^n,mathrm{d}t=left(sqrt{frac{pi n}{2}}+frac23right),n^ne^{-n}+O(n^{n-1/2}e^{-n})tag{9}
$$
The argument above can be used to prove Stirling's approximation, which says that
$$
n!=sqrt{2pi n},n^ne^{-n}+O(n^{n-1/2}e^{-n})tag{10}
$$
Combining $(9)$ and $(10)$ yields
$$
begin{align}
e^{-n}sum_{k=0}^nfrac{n^k}{k!}
&=frac{1}{n!}int_n^infty e^{-t},t^n,mathrm{d}t\
&=frac12+frac{2/3}{sqrt{2pi n}}+O(n^{-1})tag{11}
end{align}
$$
answered Jun 19 '12 at 15:29
robjohn♦robjohn
268k27308632
$endgroup$
1
$begingroup$
Would the downvoter care to comment (he asked, expecting the answer "no")?
$endgroup$
– robjohn♦
May 12 '18 at 14:01
$begingroup$
hey rob, sadly the link in your answer is dead :(
$endgroup$
– tired
Jun 10 '18 at 14:17
$begingroup$
Yeah too many downvoters here :/ I upvoted this. Very Nice answer.
$endgroup$
– mick
Jun 29 '18 at 21:49
add a comment |
$begingroup$
Integration by parts yields
$$
frac{1}{k!}int_x^infty e^{-t},t^k,mathrm{d}t=frac{1}{k!}x^ke^{-x}+frac{1}{(k-1)!}int_x^infty e^{-t},t^{k-1},mathrm{d}ttag{1}
$$
Iterating $(1)$ gives
$$
frac{1}{n!}int_x^infty e^{-t},t^n,mathrm{d}t=e^{-x}sum_{k=0}^nfrac{x^k}{k!}tag{2}
$$
Thus, we get
$$
e^{-n}sum_{k=0}^nfrac{n^k}{k!}=frac{1}{n!}int_n^infty e^{-t},t^n,mathrm{d}ttag{3}
$$
Now, I will reproduce part of the argument I give here, which develops a full asymptotic expansion. Additionally, I include some error estimates that were previously missing.
$$
begin{align}
int_n^infty e^{-t},t^n,mathrm{d}t
&=n^{n+1}e^{-n}int_0^infty e^{-ns},(s+1)^n,mathrm{d}s\
&=n^{n+1}e^{-n}int_0^infty e^{-n(s-log(1+s)},mathrm{d}s\
&=n^{n+1}e^{-n}int_0^infty e^{-nu^2/2},s',mathrm{d}utag{4}
end{align}
$$
where $t=n(s+1)$ and $u^2/2=s-log(1+s)$.
Note that $frac{ss'}{1+s}=u$; thus, when $sge1$, $s'le2u$. This leads to the bound
$$
begin{align}
int_{sge1} e^{-nu^2/2},s',mathrm{d}u
&leint_{3/4}^infty e^{-nu^2/2},2u,mathrm{d}u\
&=frac2ne^{-frac98n}tag{5}
end{align}
$$
$(5)$ also show that
$$
int_{sge1}e^{-nu^2/2},mathrm{d}ulefrac2ne^{-frac98n}tag{6}
$$
For $|s|<1$, we get
$$
u^2/2=s-log(1+s)=s^2/2-s^3/3+s^4/4-dotstag{7}
$$
We can invert the series to get $s'=1+frac23u+O(u^2)$. Therefore,
$$
begin{align}
int_0^infty e^{-nu^2/2},s',mathrm{d}u
&=int_{sin[0,1]} e^{-nu^2/2},s',mathrm{d}u+color{red}{int_{s>1} e^{-nu^2/2},s',mathrm{d}u}\
&=int_0^inftyleft(1+frac23uright)e^{-nu^2/2},mathrm{d}u-color{darkorange}{int_{s>1}left(1+frac23uright)e^{-nu^2/2},mathrm{d}u}\
&+int_0^infty e^{-nu^2/2},O(u^2),mathrm{d}u-color{darkorange}{int_{s>1} e^{-nu^2/2},O(u^2),mathrm{d}u}\
&+color{red}{int_{s>1} e^{-nu^2/2},s',mathrm{d}u}\
&=sqrt{frac{pi}{2n}}+frac2{3n}+Oleft(n^{-3/2}right)tag{8}
end{align}
$$
The red and orange integrals decrease exponentially by $(5)$ and $(6)$.
Plugging $(8)$ into $(4)$ yields
$$
int_n^infty e^{-t},t^n,mathrm{d}t=left(sqrt{frac{pi n}{2}}+frac23right),n^ne^{-n}+O(n^{n-1/2}e^{-n})tag{9}
$$
The argument above can be used to prove Stirling's approximation, which says that
$$
n!=sqrt{2pi n},n^ne^{-n}+O(n^{n-1/2}e^{-n})tag{10}
$$
Combining $(9)$ and $(10)$ yields
$$
begin{align}
e^{-n}sum_{k=0}^nfrac{n^k}{k!}
&=frac{1}{n!}int_n^infty e^{-t},t^n,mathrm{d}t\
&=frac12+frac{2/3}{sqrt{2pi n}}+O(n^{-1})tag{11}
end{align}
$$
answered Jun 19 '12 at 15:29
robjohn♦robjohn
268k27308632
$endgroup$
Integration by parts yields
$$
frac{1}{k!}int_x^infty e^{-t},t^k,mathrm{d}t=frac{1}{k!}x^ke^{-x}+frac{1}{(k-1)!}int_x^infty e^{-t},t^{k-1},mathrm{d}ttag{1}
$$
Iterating $(1)$ gives
$$
frac{1}{n!}int_x^infty e^{-t},t^n,mathrm{d}t=e^{-x}sum_{k=0}^nfrac{x^k}{k!}tag{2}
$$
Thus, we get
$$
e^{-n}sum_{k=0}^nfrac{n^k}{k!}=frac{1}{n!}int_n^infty e^{-t},t^n,mathrm{d}ttag{3}
$$
Now, I will reproduce part of the argument I give here, which develops a full asymptotic expansion. Additionally, I include some error estimates that were previously missing.
$$
begin{align}
int_n^infty e^{-t},t^n,mathrm{d}t
&=n^{n+1}e^{-n}int_0^infty e^{-ns},(s+1)^n,mathrm{d}s\
&=n^{n+1}e^{-n}int_0^infty e^{-n(s-log(1+s)},mathrm{d}s\
&=n^{n+1}e^{-n}int_0^infty e^{-nu^2/2},s',mathrm{d}utag{4}
end{align}
$$
where $t=n(s+1)$ and $u^2/2=s-log(1+s)$.
Note that $frac{ss'}{1+s}=u$; thus, when $sge1$, $s'le2u$. This leads to the bound
$$
begin{align}
int_{sge1} e^{-nu^2/2},s',mathrm{d}u
&leint_{3/4}^infty e^{-nu^2/2},2u,mathrm{d}u\
&=frac2ne^{-frac98n}tag{5}
end{align}
$$
$(5)$ also show that
$$
int_{sge1}e^{-nu^2/2},mathrm{d}ulefrac2ne^{-frac98n}tag{6}
$$
For $|s|<1$, we get
$$
u^2/2=s-log(1+s)=s^2/2-s^3/3+s^4/4-dotstag{7}
$$
We can invert the series to get $s'=1+frac23u+O(u^2)$. Therefore,
$$
begin{align}
int_0^infty e^{-nu^2/2},s',mathrm{d}u
&=int_{sin[0,1]} e^{-nu^2/2},s',mathrm{d}u+color{red}{int_{s>1} e^{-nu^2/2},s',mathrm{d}u}\
&=int_0^inftyleft(1+frac23uright)e^{-nu^2/2},mathrm{d}u-color{darkorange}{int_{s>1}left(1+frac23uright)e^{-nu^2/2},mathrm{d}u}\
&+int_0^infty e^{-nu^2/2},O(u^2),mathrm{d}u-color{darkorange}{int_{s>1} e^{-nu^2/2},O(u^2),mathrm{d}u}\
&+color{red}{int_{s>1} e^{-nu^2/2},s',mathrm{d}u}\
&=sqrt{frac{pi}{2n}}+frac2{3n}+Oleft(n^{-3/2}right)tag{8}
end{align}
$$
The red and orange integrals decrease exponentially by $(5)$ and $(6)$.
Plugging $(8)$ into $(4)$ yields
$$
int_n^infty e^{-t},t^n,mathrm{d}t=left(sqrt{frac{pi n}{2}}+frac23right),n^ne^{-n}+O(n^{n-1/2}e^{-n})tag{9}
$$
The argument above can be used to prove Stirling's approximation, which says that
$$
n!=sqrt{2pi n},n^ne^{-n}+O(n^{n-1/2}e^{-n})tag{10}
$$
Combining $(9)$ and $(10)$ yields
$$
begin{align}
e^{-n}sum_{k=0}^nfrac{n^k}{k!}
&=frac{1}{n!}int_n^infty e^{-t},t^n,mathrm{d}t\
&=frac12+frac{2/3}{sqrt{2pi n}}+O(n^{-1})tag{11}
end{align}
$$
answered Jun 19 '12 at 15:29
robjohn♦robjohn
268k27308632
edited Oct 29 '13 at 1:32
answered Jun 19 '12 at 15:29
robjohn♦robjohn
268k27308632
answered Jun 19 '12 at 15:29
robjohn♦robjohn
268k27308632
answered Jun 19 '12 at 15:29
robjohn♦robjohn
268k27308632
268k27308632
1
$begingroup$
Would the downvoter care to comment (he asked, expecting the answer "no")?
$endgroup$
– robjohn♦
May 12 '18 at 14:01
$begingroup$
hey rob, sadly the link in your answer is dead :(
$endgroup$
– tired
Jun 10 '18 at 14:17
$begingroup$
Yeah too many downvoters here :/ I upvoted this. Very Nice answer.
$endgroup$
– mick
Jun 29 '18 at 21:49
add a comment |
1
$begingroup$
Would the downvoter care to comment (he asked, expecting the answer "no")?
$endgroup$
– robjohn♦
May 12 '18 at 14:01
$begingroup$
hey rob, sadly the link in your answer is dead :(
$endgroup$
– tired
Jun 10 '18 at 14:17
$begingroup$
Yeah too many downvoters here :/ I upvoted this. Very Nice answer.
$endgroup$
– mick
Jun 29 '18 at 21:49
1
1
$begingroup$
Would the downvoter care to comment (he asked, expecting the answer "no")?
$endgroup$
– robjohn♦
May 12 '18 at 14:01
$begingroup$
Would the downvoter care to comment (he asked, expecting the answer "no")?
$endgroup$
– robjohn♦
May 12 '18 at 14:01
$begingroup$
hey rob, sadly the link in your answer is dead :(
$endgroup$
– tired
Jun 10 '18 at 14:17
$begingroup$
hey rob, sadly the link in your answer is dead :(
$endgroup$
– tired
Jun 10 '18 at 14:17
$begingroup$
Yeah too many downvoters here :/ I upvoted this. Very Nice answer.
$endgroup$
– mick
Jun 29 '18 at 21:49
$begingroup$
Yeah too many downvoters here :/ I upvoted this. Very Nice answer.
$endgroup$
– mick
Jun 29 '18 at 21:49
add a comment |
$begingroup$
If you'd like to see formal solution using calculus methods check this article http://www.emis.de/journals/AMAPN/vol15/voros.pdf
answered Jun 19 '12 at 11:09
qoqoszqoqosz
2,7571324
$endgroup$
3
$begingroup$
I wish you had copied the article here. It seemed small enough. References have a habit of pointing to NULL over time.
$endgroup$
– steven gregory
Aug 22 '15 at 5:18
add a comment |
$begingroup$
If you'd like to see formal solution using calculus methods check this article http://www.emis.de/journals/AMAPN/vol15/voros.pdf
answered Jun 19 '12 at 11:09
qoqoszqoqosz
2,7571324
$endgroup$
3
$begingroup$
I wish you had copied the article here. It seemed small enough. References have a habit of pointing to NULL over time.
$endgroup$
– steven gregory
Aug 22 '15 at 5:18
add a comment |
$begingroup$
If you'd like to see formal solution using calculus methods check this article http://www.emis.de/journals/AMAPN/vol15/voros.pdf
answered Jun 19 '12 at 11:09
qoqoszqoqosz
2,7571324
$endgroup$
If you'd like to see formal solution using calculus methods check this article http://www.emis.de/journals/AMAPN/vol15/voros.pdf
answered Jun 19 '12 at 11:09
qoqoszqoqosz
2,7571324
answered Jun 19 '12 at 11:09
qoqoszqoqosz
2,7571324
answered Jun 19 '12 at 11:09
qoqoszqoqosz
2,7571324
answered Jun 19 '12 at 11:09
qoqoszqoqosz
2,7571324
2,7571324
3
$begingroup$
I wish you had copied the article here. It seemed small enough. References have a habit of pointing to NULL over time.
$endgroup$
– steven gregory
Aug 22 '15 at 5:18
add a comment |
3
$begingroup$
I wish you had copied the article here. It seemed small enough. References have a habit of pointing to NULL over time.
$endgroup$
– steven gregory
Aug 22 '15 at 5:18
3
3
$begingroup$
I wish you had copied the article here. It seemed small enough. References have a habit of pointing to NULL over time.
$endgroup$
– steven gregory
Aug 22 '15 at 5:18
$begingroup$
I wish you had copied the article here. It seemed small enough. References have a habit of pointing to NULL over time.
$endgroup$
– steven gregory
Aug 22 '15 at 5:18
add a comment |
$begingroup$
The sum is related to the partial exponential sum, and thus to the incomplete gamma function,
$$begin{eqnarray*}
e^{-n} sum_{k=0}^{n} frac{n^k}{k!}
&=& e^{-n} e_n(n) \
&=& frac{Gamma(n+1,n)}{Gamma(n+1)},
end{eqnarray*}$$
since $e_n(x) = sum_{k=0}^n x^k/k! = e^x Gamma(n+1,x)/Gamma(n+1)$.
But
$$begin{eqnarray*}
Gamma(n+1,n) &=& sqrt{2pi}, n^{n+1/2}e^{-n}left(frac{1}{2} + frac{1}{3}sqrt{frac{2}{npi}} + Oleft(frac{1}{n}right) right).
end{eqnarray*}$$
The first term in the asymptotic expansion for $Gamma(n+1,n)$ can be found by applying the saddle point method to
$$Gamma(n+1,n) = int_n^infty dt, t^n e^{-t}.$$
The higher order terms are in principle straightforward to compute.
Using Stirling's approximation, we find
$$e^{-n} sum_{k=0}^{n} frac{n^k}{k!}
= frac{1}{2}
+ frac{1}{3}sqrt{frac{2}{npi}}
+ Oleft(frac{1}{n}right).$$
Thus, the limit is $1/2$, as found by @sos440 and @robjohn.
This limit is a special case of DLMF 8.11.13.
I just noticed a comment that suggests this be done using high school level math.
If this is a standard exercise at your high school, maybe they covered the incomplete gamma function! ;-)
answered Jun 20 '12 at 0:22
user26872user26872
14.9k22773
$endgroup$
2
$begingroup$
(+1) I derived this asymptotic expansion here in answer to a question on sci.math. I computed a few terms past $frac12$: $$ frac12+frac{1}{sqrt{2pi n}}left(frac23-frac{23}{270n}+frac{23}{3024n^2}+dotsright) $$
$endgroup$
– robjohn♦
Jun 20 '12 at 3:14
$begingroup$
@robjohn: Thanks for the link, I'll have a look. By the way, I voted up your nice solution a couple of hours ago. I like your short and sweet derivation of (3).
$endgroup$
– user26872
Jun 20 '12 at 3:47
$begingroup$
@robjohn As steven gregory says above "I wish you had copied the article here. It seemed small enough. References have a habit of pointing to NULL over time" . Please, could you upload somewhere again? I'm curious about it.
$endgroup$
– vesszabo
Jul 4 '17 at 21:13
add a comment |
$begingroup$
The sum is related to the partial exponential sum, and thus to the incomplete gamma function,
$$begin{eqnarray*}
e^{-n} sum_{k=0}^{n} frac{n^k}{k!}
&=& e^{-n} e_n(n) \
&=& frac{Gamma(n+1,n)}{Gamma(n+1)},
end{eqnarray*}$$
since $e_n(x) = sum_{k=0}^n x^k/k! = e^x Gamma(n+1,x)/Gamma(n+1)$.
But
$$begin{eqnarray*}
Gamma(n+1,n) &=& sqrt{2pi}, n^{n+1/2}e^{-n}left(frac{1}{2} + frac{1}{3}sqrt{frac{2}{npi}} + Oleft(frac{1}{n}right) right).
end{eqnarray*}$$
The first term in the asymptotic expansion for $Gamma(n+1,n)$ can be found by applying the saddle point method to
$$Gamma(n+1,n) = int_n^infty dt, t^n e^{-t}.$$
The higher order terms are in principle straightforward to compute.
Using Stirling's approximation, we find
$$e^{-n} sum_{k=0}^{n} frac{n^k}{k!}
= frac{1}{2}
+ frac{1}{3}sqrt{frac{2}{npi}}
+ Oleft(frac{1}{n}right).$$
Thus, the limit is $1/2$, as found by @sos440 and @robjohn.
This limit is a special case of DLMF 8.11.13.
I just noticed a comment that suggests this be done using high school level math.
If this is a standard exercise at your high school, maybe they covered the incomplete gamma function! ;-)
answered Jun 20 '12 at 0:22
user26872user26872
14.9k22773
$endgroup$
2
$begingroup$
(+1) I derived this asymptotic expansion here in answer to a question on sci.math. I computed a few terms past $frac12$: $$ frac12+frac{1}{sqrt{2pi n}}left(frac23-frac{23}{270n}+frac{23}{3024n^2}+dotsright) $$
$endgroup$
– robjohn♦
Jun 20 '12 at 3:14
$begingroup$
@robjohn: Thanks for the link, I'll have a look. By the way, I voted up your nice solution a couple of hours ago. I like your short and sweet derivation of (3).
$endgroup$
– user26872
Jun 20 '12 at 3:47
$begingroup$
@robjohn As steven gregory says above "I wish you had copied the article here. It seemed small enough. References have a habit of pointing to NULL over time" . Please, could you upload somewhere again? I'm curious about it.
$endgroup$
– vesszabo
Jul 4 '17 at 21:13
add a comment |
$begingroup$
The sum is related to the partial exponential sum, and thus to the incomplete gamma function,
$$begin{eqnarray*}
e^{-n} sum_{k=0}^{n} frac{n^k}{k!}
&=& e^{-n} e_n(n) \
&=& frac{Gamma(n+1,n)}{Gamma(n+1)},
end{eqnarray*}$$
since $e_n(x) = sum_{k=0}^n x^k/k! = e^x Gamma(n+1,x)/Gamma(n+1)$.
But
$$begin{eqnarray*}
Gamma(n+1,n) &=& sqrt{2pi}, n^{n+1/2}e^{-n}left(frac{1}{2} + frac{1}{3}sqrt{frac{2}{npi}} + Oleft(frac{1}{n}right) right).
end{eqnarray*}$$
The first term in the asymptotic expansion for $Gamma(n+1,n)$ can be found by applying the saddle point method to
$$Gamma(n+1,n) = int_n^infty dt, t^n e^{-t}.$$
The higher order terms are in principle straightforward to compute.
Using Stirling's approximation, we find
$$e^{-n} sum_{k=0}^{n} frac{n^k}{k!}
= frac{1}{2}
+ frac{1}{3}sqrt{frac{2}{npi}}
+ Oleft(frac{1}{n}right).$$
Thus, the limit is $1/2$, as found by @sos440 and @robjohn.
This limit is a special case of DLMF 8.11.13.
I just noticed a comment that suggests this be done using high school level math.
If this is a standard exercise at your high school, maybe they covered the incomplete gamma function! ;-)
answered Jun 20 '12 at 0:22
user26872user26872
14.9k22773
$endgroup$
The sum is related to the partial exponential sum, and thus to the incomplete gamma function,
$$begin{eqnarray*}
e^{-n} sum_{k=0}^{n} frac{n^k}{k!}
&=& e^{-n} e_n(n) \
&=& frac{Gamma(n+1,n)}{Gamma(n+1)},
end{eqnarray*}$$
since $e_n(x) = sum_{k=0}^n x^k/k! = e^x Gamma(n+1,x)/Gamma(n+1)$.
But
$$begin{eqnarray*}
Gamma(n+1,n) &=& sqrt{2pi}, n^{n+1/2}e^{-n}left(frac{1}{2} + frac{1}{3}sqrt{frac{2}{npi}} + Oleft(frac{1}{n}right) right).
end{eqnarray*}$$
The first term in the asymptotic expansion for $Gamma(n+1,n)$ can be found by applying the saddle point method to
$$Gamma(n+1,n) = int_n^infty dt, t^n e^{-t}.$$
The higher order terms are in principle straightforward to compute.
Using Stirling's approximation, we find
$$e^{-n} sum_{k=0}^{n} frac{n^k}{k!}
= frac{1}{2}
+ frac{1}{3}sqrt{frac{2}{npi}}
+ Oleft(frac{1}{n}right).$$
Thus, the limit is $1/2$, as found by @sos440 and @robjohn.
This limit is a special case of DLMF 8.11.13.
I just noticed a comment that suggests this be done using high school level math.
If this is a standard exercise at your high school, maybe they covered the incomplete gamma function! ;-)
answered Jun 20 '12 at 0:22
user26872user26872
14.9k22773
answered Jun 20 '12 at 0:22
user26872user26872
14.9k22773
answered Jun 20 '12 at 0:22
user26872user26872
14.9k22773
answered Jun 20 '12 at 0:22
user26872user26872
14.9k22773
14.9k22773
2
$begingroup$
(+1) I derived this asymptotic expansion here in answer to a question on sci.math. I computed a few terms past $frac12$: $$ frac12+frac{1}{sqrt{2pi n}}left(frac23-frac{23}{270n}+frac{23}{3024n^2}+dotsright) $$
$endgroup$
– robjohn♦
Jun 20 '12 at 3:14
$begingroup$
@robjohn: Thanks for the link, I'll have a look. By the way, I voted up your nice solution a couple of hours ago. I like your short and sweet derivation of (3).
$endgroup$
– user26872
Jun 20 '12 at 3:47
$begingroup$
@robjohn As steven gregory says above "I wish you had copied the article here. It seemed small enough. References have a habit of pointing to NULL over time" . Please, could you upload somewhere again? I'm curious about it.
$endgroup$
– vesszabo
Jul 4 '17 at 21:13
add a comment |
2
$begingroup$
(+1) I derived this asymptotic expansion here in answer to a question on sci.math. I computed a few terms past $frac12$: $$ frac12+frac{1}{sqrt{2pi n}}left(frac23-frac{23}{270n}+frac{23}{3024n^2}+dotsright) $$
$endgroup$
– robjohn♦
Jun 20 '12 at 3:14
$begingroup$
@robjohn: Thanks for the link, I'll have a look. By the way, I voted up your nice solution a couple of hours ago. I like your short and sweet derivation of (3).
$endgroup$
– user26872
Jun 20 '12 at 3:47
$begingroup$
@robjohn As steven gregory says above "I wish you had copied the article here. It seemed small enough. References have a habit of pointing to NULL over time" . Please, could you upload somewhere again? I'm curious about it.
$endgroup$
– vesszabo
Jul 4 '17 at 21:13
2
2
$begingroup$
(+1) I derived this asymptotic expansion here in answer to a question on sci.math. I computed a few terms past $frac12$: $$ frac12+frac{1}{sqrt{2pi n}}left(frac23-frac{23}{270n}+frac{23}{3024n^2}+dotsright) $$
$endgroup$
– robjohn♦
Jun 20 '12 at 3:14
$begingroup$
(+1) I derived this asymptotic expansion here in answer to a question on sci.math. I computed a few terms past $frac12$: $$ frac12+frac{1}{sqrt{2pi n}}left(frac23-frac{23}{270n}+frac{23}{3024n^2}+dotsright) $$
$endgroup$
– robjohn♦
Jun 20 '12 at 3:14
$begingroup$
@robjohn: Thanks for the link, I'll have a look. By the way, I voted up your nice solution a couple of hours ago. I like your short and sweet derivation of (3).
$endgroup$
– user26872
Jun 20 '12 at 3:47
$begingroup$
@robjohn: Thanks for the link, I'll have a look. By the way, I voted up your nice solution a couple of hours ago. I like your short and sweet derivation of (3).
$endgroup$
– user26872
Jun 20 '12 at 3:47
$begingroup$
@robjohn As steven gregory says above "I wish you had copied the article here. It seemed small enough. References have a habit of pointing to NULL over time" . Please, could you upload somewhere again? I'm curious about it.
$endgroup$
– vesszabo
Jul 4 '17 at 21:13
$begingroup$
@robjohn As steven gregory says above "I wish you had copied the article here. It seemed small enough. References have a habit of pointing to NULL over time" . Please, could you upload somewhere again? I'm curious about it.
$endgroup$
– vesszabo
Jul 4 '17 at 21:13
add a comment |
$begingroup$
$newcommand{+}{^{dagger}}
newcommand{angles}[1]{leftlangle #1 rightrangle}
newcommand{braces}[1]{leftlbrace #1 rightrbrace}
newcommand{bracks}[1]{leftlbrack #1 rightrbrack}
newcommand{dd}{{rm d}}
newcommand{isdiv}{,left.rightvert,}
newcommand{ds}[1]{displaystyle{#1}}
newcommand{equalby}[1]{{#1 atop {= atop vphantom{huge A}}}}
newcommand{expo}[1]{,{rm e}^{#1},}
newcommand{floor}[1]{,leftlfloor #1 rightrfloor,}
newcommand{half}{{1 over 2}}
newcommand{ic}{{rm i}}
newcommand{imp}{Longrightarrow}
newcommand{ket}[1]{leftvert #1rightrangle}
newcommand{pars}[1]{left( #1 right)}
newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
newcommand{pp}{{cal P}}
newcommand{root}[2]{,sqrt[#1]{,#2,},}
newcommand{sech}{,{rm sech}}
newcommand{sgn}{,{rm sgn}}
newcommand{totald}[3]{frac{{rm d}^{#1} #2}{{rm d} #3^{#1}}}
newcommand{ul}[1]{underline{#1}}
newcommand{verts}[1]{leftvert #1 rightvert}
newcommand{yy}{Longleftrightarrow}$
begin{align}&color{#00f}{
lim_{n to infty}bracks{expo{-n}sum_{k = 0}^{n}{n^{k} over k!}}}
\[3mm]&=lim_{n to infty}bracks{expo{-n}sum_{k = 0}^{n}
exppars{klnpars{n} - lnpars{k!}}}
\[3mm]&=
lim_{n to infty}braces{expo{-n}sum_{k = 0}^{n}
exppars{nlnpars{n} - lnpars{n!} - {1 over 2n}bracks{k - n}^{2}}}
\[3mm]&=
lim_{n to infty}braces{expo{-n},{n^{n} over n!}sum_{k = 0}^{n}
exppars{-{1 over 2n}bracks{k - n}^{2}}}
\[3mm]&=
lim_{n to infty}braces{{expo{-n}n^{n} over n!}int_{0}^{n}
exppars{-{1 over 2n}bracks{k - n}^{2}},dd k}
\[3mm]&=
lim_{n to infty}bracks{{expo{-n}n^{n} over n!}int_{-n}^{0}
exppars{-,{k^{2} over 2n}},dd k}
=
lim_{n to infty}bracks{{expo{-n}n^{n} over n!},root{2n}
int_{-root{n}/2}^{0}exppars{-k^{2}},dd k}
\[3mm]&=
lim_{n to infty}bracks{{root{2}n^{n + 1/2}expo{-n} over n!}
int_{-infty}^{0}exppars{-k^{2}},dd k}
=
lim_{n to infty}bracks{{root{2}n^{n + 1/2}expo{-n} over n!}
,{root{pi} over 2}}
\[3mm]&=
half,lim_{n to infty}bracks{{root{2pi}n^{n + 1/2}expo{-n} over n!}}
=color{#00f}{Largehalf}
end{align}
edited May 25 '15 at 4:02
Lucian
41.2k159130
answered Nov 12 '13 at 15:20
Felix MarinFelix Marin
68k7107142
$endgroup$
15
$begingroup$
The second equal sign is a complete mystery. The passage from a sum to an integral also needs justification but it probably holds.
$endgroup$
– Did
Mar 31 '14 at 16:25
9
$begingroup$
Would you care answering @Did 's question regarding the second equal sign? I am miffed as well. Thank you, Felix Marin.
$endgroup$
– Hans
May 11 '15 at 17:35
4
$begingroup$
@Did's question has to be answered otherwise this seems to be an suitable answer
$endgroup$
– tired
Oct 4 '15 at 12:12
3
$begingroup$
yeah for me too, can you please answer @Did 's question?
$endgroup$
– user153330
Mar 1 '16 at 20:40
1
$begingroup$
Is this supposed to justify the various unsubstantiated claims this post relies on? It does not.
$endgroup$
– Did
Feb 8 '18 at 17:56
|
show 2 more comments
$begingroup$
$newcommand{+}{^{dagger}}
newcommand{angles}[1]{leftlangle #1 rightrangle}
newcommand{braces}[1]{leftlbrace #1 rightrbrace}
newcommand{bracks}[1]{leftlbrack #1 rightrbrack}
newcommand{dd}{{rm d}}
newcommand{isdiv}{,left.rightvert,}
newcommand{ds}[1]{displaystyle{#1}}
newcommand{equalby}[1]{{#1 atop {= atop vphantom{huge A}}}}
newcommand{expo}[1]{,{rm e}^{#1},}
newcommand{floor}[1]{,leftlfloor #1 rightrfloor,}
newcommand{half}{{1 over 2}}
newcommand{ic}{{rm i}}
newcommand{imp}{Longrightarrow}
newcommand{ket}[1]{leftvert #1rightrangle}
newcommand{pars}[1]{left( #1 right)}
newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
newcommand{pp}{{cal P}}
newcommand{root}[2]{,sqrt[#1]{,#2,},}
newcommand{sech}{,{rm sech}}
newcommand{sgn}{,{rm sgn}}
newcommand{totald}[3]{frac{{rm d}^{#1} #2}{{rm d} #3^{#1}}}
newcommand{ul}[1]{underline{#1}}
newcommand{verts}[1]{leftvert #1 rightvert}
newcommand{yy}{Longleftrightarrow}$
begin{align}&color{#00f}{
lim_{n to infty}bracks{expo{-n}sum_{k = 0}^{n}{n^{k} over k!}}}
\[3mm]&=lim_{n to infty}bracks{expo{-n}sum_{k = 0}^{n}
exppars{klnpars{n} - lnpars{k!}}}
\[3mm]&=
lim_{n to infty}braces{expo{-n}sum_{k = 0}^{n}
exppars{nlnpars{n} - lnpars{n!} - {1 over 2n}bracks{k - n}^{2}}}
\[3mm]&=
lim_{n to infty}braces{expo{-n},{n^{n} over n!}sum_{k = 0}^{n}
exppars{-{1 over 2n}bracks{k - n}^{2}}}
\[3mm]&=
lim_{n to infty}braces{{expo{-n}n^{n} over n!}int_{0}^{n}
exppars{-{1 over 2n}bracks{k - n}^{2}},dd k}
\[3mm]&=
lim_{n to infty}bracks{{expo{-n}n^{n} over n!}int_{-n}^{0}
exppars{-,{k^{2} over 2n}},dd k}
=
lim_{n to infty}bracks{{expo{-n}n^{n} over n!},root{2n}
int_{-root{n}/2}^{0}exppars{-k^{2}},dd k}
\[3mm]&=
lim_{n to infty}bracks{{root{2}n^{n + 1/2}expo{-n} over n!}
int_{-infty}^{0}exppars{-k^{2}},dd k}
=
lim_{n to infty}bracks{{root{2}n^{n + 1/2}expo{-n} over n!}
,{root{pi} over 2}}
\[3mm]&=
half,lim_{n to infty}bracks{{root{2pi}n^{n + 1/2}expo{-n} over n!}}
=color{#00f}{Largehalf}
end{align}
edited May 25 '15 at 4:02
Lucian
41.2k159130
answered Nov 12 '13 at 15:20
Felix MarinFelix Marin
68k7107142
$endgroup$
15
$begingroup$
The second equal sign is a complete mystery. The passage from a sum to an integral also needs justification but it probably holds.
$endgroup$
– Did
Mar 31 '14 at 16:25
9
$begingroup$
Would you care answering @Did 's question regarding the second equal sign? I am miffed as well. Thank you, Felix Marin.
$endgroup$
– Hans
May 11 '15 at 17:35
4
$begingroup$
@Did's question has to be answered otherwise this seems to be an suitable answer
$endgroup$
– tired
Oct 4 '15 at 12:12
3
$begingroup$
yeah for me too, can you please answer @Did 's question?
$endgroup$
– user153330
Mar 1 '16 at 20:40
1
$begingroup$
Is this supposed to justify the various unsubstantiated claims this post relies on? It does not.
$endgroup$
– Did
Feb 8 '18 at 17:56
|
show 2 more comments
$begingroup$
$newcommand{+}{^{dagger}}
newcommand{angles}[1]{leftlangle #1 rightrangle}
newcommand{braces}[1]{leftlbrace #1 rightrbrace}
newcommand{bracks}[1]{leftlbrack #1 rightrbrack}
newcommand{dd}{{rm d}}
newcommand{isdiv}{,left.rightvert,}
newcommand{ds}[1]{displaystyle{#1}}
newcommand{equalby}[1]{{#1 atop {= atop vphantom{huge A}}}}
newcommand{expo}[1]{,{rm e}^{#1},}
newcommand{floor}[1]{,leftlfloor #1 rightrfloor,}
newcommand{half}{{1 over 2}}
newcommand{ic}{{rm i}}
newcommand{imp}{Longrightarrow}
newcommand{ket}[1]{leftvert #1rightrangle}
newcommand{pars}[1]{left( #1 right)}
newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
newcommand{pp}{{cal P}}
newcommand{root}[2]{,sqrt[#1]{,#2,},}
newcommand{sech}{,{rm sech}}
newcommand{sgn}{,{rm sgn}}
newcommand{totald}[3]{frac{{rm d}^{#1} #2}{{rm d} #3^{#1}}}
newcommand{ul}[1]{underline{#1}}
newcommand{verts}[1]{leftvert #1 rightvert}
newcommand{yy}{Longleftrightarrow}$
begin{align}&color{#00f}{
lim_{n to infty}bracks{expo{-n}sum_{k = 0}^{n}{n^{k} over k!}}}
\[3mm]&=lim_{n to infty}bracks{expo{-n}sum_{k = 0}^{n}
exppars{klnpars{n} - lnpars{k!}}}
\[3mm]&=
lim_{n to infty}braces{expo{-n}sum_{k = 0}^{n}
exppars{nlnpars{n} - lnpars{n!} - {1 over 2n}bracks{k - n}^{2}}}
\[3mm]&=
lim_{n to infty}braces{expo{-n},{n^{n} over n!}sum_{k = 0}^{n}
exppars{-{1 over 2n}bracks{k - n}^{2}}}
\[3mm]&=
lim_{n to infty}braces{{expo{-n}n^{n} over n!}int_{0}^{n}
exppars{-{1 over 2n}bracks{k - n}^{2}},dd k}
\[3mm]&=
lim_{n to infty}bracks{{expo{-n}n^{n} over n!}int_{-n}^{0}
exppars{-,{k^{2} over 2n}},dd k}
=
lim_{n to infty}bracks{{expo{-n}n^{n} over n!},root{2n}
int_{-root{n}/2}^{0}exppars{-k^{2}},dd k}
\[3mm]&=
lim_{n to infty}bracks{{root{2}n^{n + 1/2}expo{-n} over n!}
int_{-infty}^{0}exppars{-k^{2}},dd k}
=
lim_{n to infty}bracks{{root{2}n^{n + 1/2}expo{-n} over n!}
,{root{pi} over 2}}
\[3mm]&=
half,lim_{n to infty}bracks{{root{2pi}n^{n + 1/2}expo{-n} over n!}}
=color{#00f}{Largehalf}
end{align}
edited May 25 '15 at 4:02
Lucian
41.2k159130
answered Nov 12 '13 at 15:20
Felix MarinFelix Marin
68k7107142
$endgroup$
$newcommand{+}{^{dagger}}
newcommand{angles}[1]{leftlangle #1 rightrangle}
newcommand{braces}[1]{leftlbrace #1 rightrbrace}
newcommand{bracks}[1]{leftlbrack #1 rightrbrack}
newcommand{dd}{{rm d}}
newcommand{isdiv}{,left.rightvert,}
newcommand{ds}[1]{displaystyle{#1}}
newcommand{equalby}[1]{{#1 atop {= atop vphantom{huge A}}}}
newcommand{expo}[1]{,{rm e}^{#1},}
newcommand{floor}[1]{,leftlfloor #1 rightrfloor,}
newcommand{half}{{1 over 2}}
newcommand{ic}{{rm i}}
newcommand{imp}{Longrightarrow}
newcommand{ket}[1]{leftvert #1rightrangle}
newcommand{pars}[1]{left( #1 right)}
newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
newcommand{pp}{{cal P}}
newcommand{root}[2]{,sqrt[#1]{,#2,},}
newcommand{sech}{,{rm sech}}
newcommand{sgn}{,{rm sgn}}
newcommand{totald}[3]{frac{{rm d}^{#1} #2}{{rm d} #3^{#1}}}
newcommand{ul}[1]{underline{#1}}
newcommand{verts}[1]{leftvert #1 rightvert}
newcommand{yy}{Longleftrightarrow}$
begin{align}&color{#00f}{
lim_{n to infty}bracks{expo{-n}sum_{k = 0}^{n}{n^{k} over k!}}}
\[3mm]&=lim_{n to infty}bracks{expo{-n}sum_{k = 0}^{n}
exppars{klnpars{n} - lnpars{k!}}}
\[3mm]&=
lim_{n to infty}braces{expo{-n}sum_{k = 0}^{n}
exppars{nlnpars{n} - lnpars{n!} - {1 over 2n}bracks{k - n}^{2}}}
\[3mm]&=
lim_{n to infty}braces{expo{-n},{n^{n} over n!}sum_{k = 0}^{n}
exppars{-{1 over 2n}bracks{k - n}^{2}}}
\[3mm]&=
lim_{n to infty}braces{{expo{-n}n^{n} over n!}int_{0}^{n}
exppars{-{1 over 2n}bracks{k - n}^{2}},dd k}
\[3mm]&=
lim_{n to infty}bracks{{expo{-n}n^{n} over n!}int_{-n}^{0}
exppars{-,{k^{2} over 2n}},dd k}
=
lim_{n to infty}bracks{{expo{-n}n^{n} over n!},root{2n}
int_{-root{n}/2}^{0}exppars{-k^{2}},dd k}
\[3mm]&=
lim_{n to infty}bracks{{root{2}n^{n + 1/2}expo{-n} over n!}
int_{-infty}^{0}exppars{-k^{2}},dd k}
=
lim_{n to infty}bracks{{root{2}n^{n + 1/2}expo{-n} over n!}
,{root{pi} over 2}}
\[3mm]&=
half,lim_{n to infty}bracks{{root{2pi}n^{n + 1/2}expo{-n} over n!}}
=color{#00f}{Largehalf}
end{align}
edited May 25 '15 at 4:02
Lucian
41.2k159130
answered Nov 12 '13 at 15:20
Felix MarinFelix Marin
68k7107142
edited May 25 '15 at 4:02
Lucian
41.2k159130
edited May 25 '15 at 4:02
Lucian
41.2k159130
edited May 25 '15 at 4:02
Lucian
41.2k159130
41.2k159130
answered Nov 12 '13 at 15:20
Felix MarinFelix Marin
68k7107142
answered Nov 12 '13 at 15:20
Felix MarinFelix Marin
68k7107142
answered Nov 12 '13 at 15:20
Felix MarinFelix Marin
68k7107142
68k7107142
15
$begingroup$
The second equal sign is a complete mystery. The passage from a sum to an integral also needs justification but it probably holds.
$endgroup$
– Did
Mar 31 '14 at 16:25
9
$begingroup$
Would you care answering @Did 's question regarding the second equal sign? I am miffed as well. Thank you, Felix Marin.
$endgroup$
– Hans
May 11 '15 at 17:35
4
$begingroup$
@Did's question has to be answered otherwise this seems to be an suitable answer
$endgroup$
– tired
Oct 4 '15 at 12:12
3
$begingroup$
yeah for me too, can you please answer @Did 's question?
$endgroup$
– user153330
Mar 1 '16 at 20:40
1
$begingroup$
Is this supposed to justify the various unsubstantiated claims this post relies on? It does not.
$endgroup$
– Did
Feb 8 '18 at 17:56
|
show 2 more comments
15
$begingroup$
The second equal sign is a complete mystery. The passage from a sum to an integral also needs justification but it probably holds.
$endgroup$
– Did
Mar 31 '14 at 16:25
9
$begingroup$
Would you care answering @Did 's question regarding the second equal sign? I am miffed as well. Thank you, Felix Marin.
$endgroup$
– Hans
May 11 '15 at 17:35
4
$begingroup$
@Did's question has to be answered otherwise this seems to be an suitable answer
$endgroup$
– tired
Oct 4 '15 at 12:12
3
$begingroup$
yeah for me too, can you please answer @Did 's question?
$endgroup$
– user153330
Mar 1 '16 at 20:40
1
$begingroup$
Is this supposed to justify the various unsubstantiated claims this post relies on? It does not.
$endgroup$
– Did
Feb 8 '18 at 17:56
15
15
$begingroup$
The second equal sign is a complete mystery. The passage from a sum to an integral also needs justification but it probably holds.
$endgroup$
– Did
Mar 31 '14 at 16:25
$begingroup$
The second equal sign is a complete mystery. The passage from a sum to an integral also needs justification but it probably holds.
$endgroup$
– Did
Mar 31 '14 at 16:25
9
9
$begingroup$
Would you care answering @Did 's question regarding the second equal sign? I am miffed as well. Thank you, Felix Marin.
$endgroup$
– Hans
May 11 '15 at 17:35
$begingroup$
Would you care answering @Did 's question regarding the second equal sign? I am miffed as well. Thank you, Felix Marin.
$endgroup$
– Hans
May 11 '15 at 17:35
4
4
$begingroup$
@Did's question has to be answered otherwise this seems to be an suitable answer
$endgroup$
– tired
Oct 4 '15 at 12:12
$begingroup$
@Did's question has to be answered otherwise this seems to be an suitable answer
$endgroup$
– tired
Oct 4 '15 at 12:12
3
3
$begingroup$
yeah for me too, can you please answer @Did 's question?
$endgroup$
– user153330
Mar 1 '16 at 20:40
$begingroup$
yeah for me too, can you please answer @Did 's question?
$endgroup$
– user153330
Mar 1 '16 at 20:40
1
1
$begingroup$
Is this supposed to justify the various unsubstantiated claims this post relies on? It does not.
$endgroup$
– Did
Feb 8 '18 at 17:56
$begingroup$
Is this supposed to justify the various unsubstantiated claims this post relies on? It does not.
$endgroup$
– Did
Feb 8 '18 at 17:56
|
show 2 more comments
$begingroup$
I'll give you two hints:
1) Poisson distributions;
2) Central limit theorem
I am not aware of any other technique to solve the problem, so any other answer is appreciated.
edited Jun 19 '12 at 10:53
DonAntonio
178k1494230
answered Jun 19 '12 at 9:50
D. ThomineD. Thomine
7,5691538
$endgroup$
3
$begingroup$
In what country's education system is this a high school exercise?! I ask sincerely because I'm interested in that, and my experience is that even some of the most advanced mathematically education systems don't reach exercises as the one you're proposing...not even close. Of course, I don't know all the education systems (not even close, again), but the expression within the sum seems to be pretty tough...it reminds the series for the exponential function, but that n repeating in the numerator and upper limit...are you sure the expression is accurate?
$endgroup$
– DonAntonio
Jun 19 '12 at 10:17
2
$begingroup$
This problem is definitely not at high-school level. Without the hints I gave, I doubt most university students (even graduates) would solve it in reasonable time.
$endgroup$
– D. Thomine
Jun 19 '12 at 10:43
$begingroup$
The solution using Poisson distribution was also given here: Limit using Poisson distribution
$endgroup$
– Martin Sleziak
Jun 19 '12 at 15:44
$begingroup$
We actually made this exercice in our probability course.
$endgroup$
– Math_QED
Nov 26 '18 at 10:09
add a comment |
$begingroup$
I'll give you two hints:
1) Poisson distributions;
2) Central limit theorem
I am not aware of any other technique to solve the problem, so any other answer is appreciated.
edited Jun 19 '12 at 10:53
DonAntonio
178k1494230
answered Jun 19 '12 at 9:50
D. ThomineD. Thomine
7,5691538
$endgroup$
3
$begingroup$
In what country's education system is this a high school exercise?! I ask sincerely because I'm interested in that, and my experience is that even some of the most advanced mathematically education systems don't reach exercises as the one you're proposing...not even close. Of course, I don't know all the education systems (not even close, again), but the expression within the sum seems to be pretty tough...it reminds the series for the exponential function, but that n repeating in the numerator and upper limit...are you sure the expression is accurate?
$endgroup$
– DonAntonio
Jun 19 '12 at 10:17
2
$begingroup$
This problem is definitely not at high-school level. Without the hints I gave, I doubt most university students (even graduates) would solve it in reasonable time.
$endgroup$
– D. Thomine
Jun 19 '12 at 10:43
$begingroup$
The solution using Poisson distribution was also given here: Limit using Poisson distribution
$endgroup$
– Martin Sleziak
Jun 19 '12 at 15:44
$begingroup$
We actually made this exercice in our probability course.
$endgroup$
– Math_QED
Nov 26 '18 at 10:09
add a comment |
$begingroup$
I'll give you two hints:
1) Poisson distributions;
2) Central limit theorem
I am not aware of any other technique to solve the problem, so any other answer is appreciated.
edited Jun 19 '12 at 10:53
DonAntonio
178k1494230
answered Jun 19 '12 at 9:50
D. ThomineD. Thomine
7,5691538
$endgroup$
I'll give you two hints:
1) Poisson distributions;
2) Central limit theorem
I am not aware of any other technique to solve the problem, so any other answer is appreciated.
edited Jun 19 '12 at 10:53
DonAntonio
178k1494230
answered Jun 19 '12 at 9:50
D. ThomineD. Thomine
7,5691538
edited Jun 19 '12 at 10:53
DonAntonio
178k1494230
edited Jun 19 '12 at 10:53
DonAntonio
178k1494230
edited Jun 19 '12 at 10:53
DonAntonio
178k1494230
178k1494230
answered Jun 19 '12 at 9:50
D. ThomineD. Thomine
7,5691538
answered Jun 19 '12 at 9:50
D. ThomineD. Thomine
7,5691538
answered Jun 19 '12 at 9:50
D. ThomineD. Thomine
7,5691538
7,5691538
3
$begingroup$
In what country's education system is this a high school exercise?! I ask sincerely because I'm interested in that, and my experience is that even some of the most advanced mathematically education systems don't reach exercises as the one you're proposing...not even close. Of course, I don't know all the education systems (not even close, again), but the expression within the sum seems to be pretty tough...it reminds the series for the exponential function, but that n repeating in the numerator and upper limit...are you sure the expression is accurate?
$endgroup$
– DonAntonio
Jun 19 '12 at 10:17
2
$begingroup$
This problem is definitely not at high-school level. Without the hints I gave, I doubt most university students (even graduates) would solve it in reasonable time.
$endgroup$
– D. Thomine
Jun 19 '12 at 10:43
$begingroup$
The solution using Poisson distribution was also given here: Limit using Poisson distribution
$endgroup$
– Martin Sleziak
Jun 19 '12 at 15:44
$begingroup$
We actually made this exercice in our probability course.
$endgroup$
– Math_QED
Nov 26 '18 at 10:09
add a comment |
3
$begingroup$
In what country's education system is this a high school exercise?! I ask sincerely because I'm interested in that, and my experience is that even some of the most advanced mathematically education systems don't reach exercises as the one you're proposing...not even close. Of course, I don't know all the education systems (not even close, again), but the expression within the sum seems to be pretty tough...it reminds the series for the exponential function, but that n repeating in the numerator and upper limit...are you sure the expression is accurate?
$endgroup$
– DonAntonio
Jun 19 '12 at 10:17
2
$begingroup$
This problem is definitely not at high-school level. Without the hints I gave, I doubt most university students (even graduates) would solve it in reasonable time.
$endgroup$
– D. Thomine
Jun 19 '12 at 10:43
$begingroup$
The solution using Poisson distribution was also given here: Limit using Poisson distribution
$endgroup$
– Martin Sleziak
Jun 19 '12 at 15:44
$begingroup$
We actually made this exercice in our probability course.
$endgroup$
– Math_QED
Nov 26 '18 at 10:09
3
3
$begingroup$
In what country's education system is this a high school exercise?! I ask sincerely because I'm interested in that, and my experience is that even some of the most advanced mathematically education systems don't reach exercises as the one you're proposing...not even close. Of course, I don't know all the education systems (not even close, again), but the expression within the sum seems to be pretty tough...it reminds the series for the exponential function, but that n repeating in the numerator and upper limit...are you sure the expression is accurate?
$endgroup$
– DonAntonio
Jun 19 '12 at 10:17
$begingroup$
In what country's education system is this a high school exercise?! I ask sincerely because I'm interested in that, and my experience is that even some of the most advanced mathematically education systems don't reach exercises as the one you're proposing...not even close. Of course, I don't know all the education systems (not even close, again), but the expression within the sum seems to be pretty tough...it reminds the series for the exponential function, but that n repeating in the numerator and upper limit...are you sure the expression is accurate?
$endgroup$
– DonAntonio
Jun 19 '12 at 10:17
2
2
$begingroup$
This problem is definitely not at high-school level. Without the hints I gave, I doubt most university students (even graduates) would solve it in reasonable time.
$endgroup$
– D. Thomine
Jun 19 '12 at 10:43
$begingroup$
This problem is definitely not at high-school level. Without the hints I gave, I doubt most university students (even graduates) would solve it in reasonable time.
$endgroup$
– D. Thomine
Jun 19 '12 at 10:43
$begingroup$
The solution using Poisson distribution was also given here: Limit using Poisson distribution
$endgroup$
– Martin Sleziak
Jun 19 '12 at 15:44
$begingroup$
The solution using Poisson distribution was also given here: Limit using Poisson distribution
$endgroup$
– Martin Sleziak
Jun 19 '12 at 15:44
$begingroup$
We actually made this exercice in our probability course.
$endgroup$
– Math_QED
Nov 26 '18 at 10:09
$begingroup$
We actually made this exercice in our probability course.
$endgroup$
– Math_QED
Nov 26 '18 at 10:09
add a comment |
$begingroup$
I do not know how much this will help you.
For a given $n$, the result is $dfrac{Gamma(n+1,n)}{n Gamma(n)}$ which has a limit equal to $dfrac12$ as $ntoinfty$.
edited May 18 '14 at 10:54
Tunk-Fey
23.1k970100
answered Sep 14 '13 at 14:33
Claude LeiboviciClaude Leibovici
121k1157133
$endgroup$
add a comment |
$begingroup$
I do not know how much this will help you.
For a given $n$, the result is $dfrac{Gamma(n+1,n)}{n Gamma(n)}$ which has a limit equal to $dfrac12$ as $ntoinfty$.
edited May 18 '14 at 10:54
Tunk-Fey
23.1k970100
answered Sep 14 '13 at 14:33
Claude LeiboviciClaude Leibovici
121k1157133
$endgroup$
add a comment |
$begingroup$
I do not know how much this will help you.
For a given $n$, the result is $dfrac{Gamma(n+1,n)}{n Gamma(n)}$ which has a limit equal to $dfrac12$ as $ntoinfty$.
edited May 18 '14 at 10:54
Tunk-Fey
23.1k970100
answered Sep 14 '13 at 14:33
Claude LeiboviciClaude Leibovici
121k1157133
$endgroup$
I do not know how much this will help you.
For a given $n$, the result is $dfrac{Gamma(n+1,n)}{n Gamma(n)}$ which has a limit equal to $dfrac12$ as $ntoinfty$.
edited May 18 '14 at 10:54
Tunk-Fey
23.1k970100
answered Sep 14 '13 at 14:33
Claude LeiboviciClaude Leibovici
121k1157133
edited May 18 '14 at 10:54
Tunk-Fey
23.1k970100
edited May 18 '14 at 10:54
Tunk-Fey
23.1k970100
edited May 18 '14 at 10:54
Tunk-Fey
23.1k970100
23.1k970100
answered Sep 14 '13 at 14:33
Claude LeiboviciClaude Leibovici
121k1157133
answered Sep 14 '13 at 14:33
Claude LeiboviciClaude Leibovici
121k1157133
answered Sep 14 '13 at 14:33
Claude LeiboviciClaude Leibovici
121k1157133
121k1157133
add a comment |
add a comment |
$begingroup$
On this page there is a nice collection of evidence.
I add another proof which also uses the Stirling formula.
$displaystyle e^{-n}sumlimits_{k=0}^nfrac{n^k}{k!} = e^{-n}sumlimits_{k=0}^nfrac{k^k (n-k)^{n-k}}{k!(n-k)!} hspace{4cm}$ e.g. here
$displaystyle = limlimits_{ntoinfty} e^{-n}sumlimits_{k=1}^{n-1}frac{e^k e^{n-k}}{sqrt{2pi k (1+mathcal{O}(1/k))}sqrt{2pi (n-k)(1+mathcal{O}(1/(n-k)))}} $
$displaystyle = limlimits_{ntoinfty} frac{1}{2pi}frac{1}{n}sumlimits_{k=1}^{n-1}frac{1}{sqrt{frac{k}{n}left(1-frac{k}{n}right)}} =frac{1}{2pi} intlimits_0^1frac{dx}{sqrt{x(1-x)}}=frac{Gamma(frac{1}{2})^2}{2pi~Gamma(1)} = frac{1}{2}$
answered Nov 26 '18 at 9:54
user90369user90369
8,188925
$endgroup$
$begingroup$
(+1) Interesting idea.
$endgroup$
– user 1357113
Nov 26 '18 at 22:23
$begingroup$
@user1357113 : That's kind of you, thanks. :)
$endgroup$
– user90369
Nov 27 '18 at 8:09
add a comment |
$begingroup$
On this page there is a nice collection of evidence.
I add another proof which also uses the Stirling formula.
$displaystyle e^{-n}sumlimits_{k=0}^nfrac{n^k}{k!} = e^{-n}sumlimits_{k=0}^nfrac{k^k (n-k)^{n-k}}{k!(n-k)!} hspace{4cm}$ e.g. here
$displaystyle = limlimits_{ntoinfty} e^{-n}sumlimits_{k=1}^{n-1}frac{e^k e^{n-k}}{sqrt{2pi k (1+mathcal{O}(1/k))}sqrt{2pi (n-k)(1+mathcal{O}(1/(n-k)))}} $
$displaystyle = limlimits_{ntoinfty} frac{1}{2pi}frac{1}{n}sumlimits_{k=1}^{n-1}frac{1}{sqrt{frac{k}{n}left(1-frac{k}{n}right)}} =frac{1}{2pi} intlimits_0^1frac{dx}{sqrt{x(1-x)}}=frac{Gamma(frac{1}{2})^2}{2pi~Gamma(1)} = frac{1}{2}$
answered Nov 26 '18 at 9:54
user90369user90369
8,188925
$endgroup$
$begingroup$
(+1) Interesting idea.
$endgroup$
– user 1357113
Nov 26 '18 at 22:23
$begingroup$
@user1357113 : That's kind of you, thanks. :)
$endgroup$
– user90369
Nov 27 '18 at 8:09
add a comment |
$begingroup$
On this page there is a nice collection of evidence.
I add another proof which also uses the Stirling formula.
$displaystyle e^{-n}sumlimits_{k=0}^nfrac{n^k}{k!} = e^{-n}sumlimits_{k=0}^nfrac{k^k (n-k)^{n-k}}{k!(n-k)!} hspace{4cm}$ e.g. here
$displaystyle = limlimits_{ntoinfty} e^{-n}sumlimits_{k=1}^{n-1}frac{e^k e^{n-k}}{sqrt{2pi k (1+mathcal{O}(1/k))}sqrt{2pi (n-k)(1+mathcal{O}(1/(n-k)))}} $
$displaystyle = limlimits_{ntoinfty} frac{1}{2pi}frac{1}{n}sumlimits_{k=1}^{n-1}frac{1}{sqrt{frac{k}{n}left(1-frac{k}{n}right)}} =frac{1}{2pi} intlimits_0^1frac{dx}{sqrt{x(1-x)}}=frac{Gamma(frac{1}{2})^2}{2pi~Gamma(1)} = frac{1}{2}$
answered Nov 26 '18 at 9:54
user90369user90369
8,188925
$endgroup$
On this page there is a nice collection of evidence.
I add another proof which also uses the Stirling formula.
$displaystyle e^{-n}sumlimits_{k=0}^nfrac{n^k}{k!} = e^{-n}sumlimits_{k=0}^nfrac{k^k (n-k)^{n-k}}{k!(n-k)!} hspace{4cm}$ e.g. here
$displaystyle = limlimits_{ntoinfty} e^{-n}sumlimits_{k=1}^{n-1}frac{e^k e^{n-k}}{sqrt{2pi k (1+mathcal{O}(1/k))}sqrt{2pi (n-k)(1+mathcal{O}(1/(n-k)))}} $
$displaystyle = limlimits_{ntoinfty} frac{1}{2pi}frac{1}{n}sumlimits_{k=1}^{n-1}frac{1}{sqrt{frac{k}{n}left(1-frac{k}{n}right)}} =frac{1}{2pi} intlimits_0^1frac{dx}{sqrt{x(1-x)}}=frac{Gamma(frac{1}{2})^2}{2pi~Gamma(1)} = frac{1}{2}$
answered Nov 26 '18 at 9:54
user90369user90369
8,188925
edited Nov 26 '18 at 10:30
answered Nov 26 '18 at 9:54
user90369user90369
8,188925
answered Nov 26 '18 at 9:54
user90369user90369
8,188925
answered Nov 26 '18 at 9:54
user90369user90369
8,188925
8,188925
$begingroup$
(+1) Interesting idea.
$endgroup$
– user 1357113
Nov 26 '18 at 22:23
$begingroup$
@user1357113 : That's kind of you, thanks. :)
$endgroup$
– user90369
Nov 27 '18 at 8:09
add a comment |
$begingroup$
(+1) Interesting idea.
$endgroup$
– user 1357113
Nov 26 '18 at 22:23
$begingroup$
@user1357113 : That's kind of you, thanks. :)
$endgroup$
– user90369
Nov 27 '18 at 8:09
$begingroup$
(+1) Interesting idea.
$endgroup$
– user 1357113
Nov 26 '18 at 22:23
$begingroup$
(+1) Interesting idea.
$endgroup$
– user 1357113
Nov 26 '18 at 22:23
$begingroup$
@user1357113 : That's kind of you, thanks. :)
$endgroup$
– user90369
Nov 27 '18 at 8:09
$begingroup$
@user1357113 : That's kind of you, thanks. :)
$endgroup$
– user90369
Nov 27 '18 at 8:09
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f160248%2fevaluating-lim-limits-n-to-infty-e-n-sum-limits-k-0n-fracnkk%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
4
$begingroup$
Related: math.stackexchange.com/questions/121099/…
$endgroup$
– leonbloy
Jun 19 '12 at 15:46
$begingroup$
This question was merged into the present one.
$endgroup$
– user642796
Oct 1 '13 at 17:16
$begingroup$
[Older question, perhaps merge...] possible duplicate of Partial sums of exponential series
$endgroup$
– Aryabhata
Jan 23 '15 at 17:46
$begingroup$
Also known as Dobiński's formula
$endgroup$
– Machinato
Jun 14 '17 at 13:08
1
$begingroup$
What is W|A , in the question. It says "by using W|A".
$endgroup$
– john
Oct 28 '18 at 10:35