Mixing
$lim_{ntoinfty} e^{-n} sum_{k=0}^{n} frac{n^k}{k!} = frac{1}{2}$ - basic methods
Prove that $$limlimits_{ntoinfty} e^{-n} sum_{k=0}^{n} frac{n^k}{k!} = frac{1}{2}$$
This problem appeared on MSE many times, but each time it was solved using Poisson distribution or lots of integrals. I am wondering, is there any way to prove it using some basic properties of limits (their arithmetics, squeeze theorem etc.), definition of $e^x$ as $limlimits_{ntoinfty}(1+frac{x}{n})^n$, basic limits with $e$, binomial expansion and logarithms, but without using integrals, series, Stirling formula, asymptotics, Taylor series?
This problem was given to me by my mathematical analysis teacher, but it's not a homework, just additional problem to think on. My teacher claims it can be solved with knowledge introduced on lectures so far, which is not much, mainly things mentioned above. Of course, I can use theorems not mentioned on the lectures, but then I have to prove them, and again, with the baisc knowledge. I've been thinking about it for a few days and couldn't do any major progress in my attempts.
calculus real-analysis limits eulers-constant
asked Nov 15 '18 at 22:43
user128409235
76315
add a comment |
Prove that $$limlimits_{ntoinfty} e^{-n} sum_{k=0}^{n} frac{n^k}{k!} = frac{1}{2}$$
This problem appeared on MSE many times, but each time it was solved using Poisson distribution or lots of integrals. I am wondering, is there any way to prove it using some basic properties of limits (their arithmetics, squeeze theorem etc.), definition of $e^x$ as $limlimits_{ntoinfty}(1+frac{x}{n})^n$, basic limits with $e$, binomial expansion and logarithms, but without using integrals, series, Stirling formula, asymptotics, Taylor series?
This problem was given to me by my mathematical analysis teacher, but it's not a homework, just additional problem to think on. My teacher claims it can be solved with knowledge introduced on lectures so far, which is not much, mainly things mentioned above. Of course, I can use theorems not mentioned on the lectures, but then I have to prove them, and again, with the baisc knowledge. I've been thinking about it for a few days and couldn't do any major progress in my attempts.
calculus real-analysis limits eulers-constant
asked Nov 15 '18 at 22:43
user128409235
76315
Previous times this question has been asked: math.stackexchange.com/questions/2603315/…, math.stackexchange.com/questions/160248/… . I'm not flagging as duplicate because the question specifically asks for basic methods.
– Michael Lugo
Nov 15 '18 at 23:42
Interestingly, the general term $n^k/k!$ is maximum when $k=n$. And by some magic, the sum "before" equals the sum "after" (asymptotically).
– Yves Daoust
Nov 18 '18 at 13:12
2
Without an algebraic miracle, I do not think there is a simple and rigorous solution. My rationale is that any solution should demonstrate the understanding on the concentration behavior of the function $k mapsto frac{n^k}{k!}e^{-n}$ around $k = n$. Both the probabilistic solution (using Poisson distribution + CLT) and the solution using integral show this. My solution is also based on this kind of observation.
– Sangchul Lee
Nov 18 '18 at 19:16
add a comment |
Prove that $$limlimits_{ntoinfty} e^{-n} sum_{k=0}^{n} frac{n^k}{k!} = frac{1}{2}$$
This problem appeared on MSE many times, but each time it was solved using Poisson distribution or lots of integrals. I am wondering, is there any way to prove it using some basic properties of limits (their arithmetics, squeeze theorem etc.), definition of $e^x$ as $limlimits_{ntoinfty}(1+frac{x}{n})^n$, basic limits with $e$, binomial expansion and logarithms, but without using integrals, series, Stirling formula, asymptotics, Taylor series?
This problem was given to me by my mathematical analysis teacher, but it's not a homework, just additional problem to think on. My teacher claims it can be solved with knowledge introduced on lectures so far, which is not much, mainly things mentioned above. Of course, I can use theorems not mentioned on the lectures, but then I have to prove them, and again, with the baisc knowledge. I've been thinking about it for a few days and couldn't do any major progress in my attempts.
calculus real-analysis limits eulers-constant
asked Nov 15 '18 at 22:43
user128409235
76315
Prove that $$limlimits_{ntoinfty} e^{-n} sum_{k=0}^{n} frac{n^k}{k!} = frac{1}{2}$$
This problem appeared on MSE many times, but each time it was solved using Poisson distribution or lots of integrals. I am wondering, is there any way to prove it using some basic properties of limits (their arithmetics, squeeze theorem etc.), definition of $e^x$ as $limlimits_{ntoinfty}(1+frac{x}{n})^n$, basic limits with $e$, binomial expansion and logarithms, but without using integrals, series, Stirling formula, asymptotics, Taylor series?
This problem was given to me by my mathematical analysis teacher, but it's not a homework, just additional problem to think on. My teacher claims it can be solved with knowledge introduced on lectures so far, which is not much, mainly things mentioned above. Of course, I can use theorems not mentioned on the lectures, but then I have to prove them, and again, with the baisc knowledge. I've been thinking about it for a few days and couldn't do any major progress in my attempts.
calculus real-analysis limits eulers-constant
calculus real-analysis limits eulers-constant
asked Nov 15 '18 at 22:43
user128409235
76315
asked Nov 15 '18 at 22:43
user128409235
76315
edited Nov 28 '18 at 22:17
asked Nov 15 '18 at 22:43
user128409235
76315
asked Nov 15 '18 at 22:43
user128409235
76315
asked Nov 15 '18 at 22:43
user128409235
76315
76315
Previous times this question has been asked: math.stackexchange.com/questions/2603315/…, math.stackexchange.com/questions/160248/… . I'm not flagging as duplicate because the question specifically asks for basic methods.
– Michael Lugo
Nov 15 '18 at 23:42
Interestingly, the general term $n^k/k!$ is maximum when $k=n$. And by some magic, the sum "before" equals the sum "after" (asymptotically).
– Yves Daoust
Nov 18 '18 at 13:12
2
Without an algebraic miracle, I do not think there is a simple and rigorous solution. My rationale is that any solution should demonstrate the understanding on the concentration behavior of the function $k mapsto frac{n^k}{k!}e^{-n}$ around $k = n$. Both the probabilistic solution (using Poisson distribution + CLT) and the solution using integral show this. My solution is also based on this kind of observation.
– Sangchul Lee
Nov 18 '18 at 19:16
add a comment |
Previous times this question has been asked: math.stackexchange.com/questions/2603315/…, math.stackexchange.com/questions/160248/… . I'm not flagging as duplicate because the question specifically asks for basic methods.
– Michael Lugo
Nov 15 '18 at 23:42
Interestingly, the general term $n^k/k!$ is maximum when $k=n$. And by some magic, the sum "before" equals the sum "after" (asymptotically).
– Yves Daoust
Nov 18 '18 at 13:12
2
Without an algebraic miracle, I do not think there is a simple and rigorous solution. My rationale is that any solution should demonstrate the understanding on the concentration behavior of the function $k mapsto frac{n^k}{k!}e^{-n}$ around $k = n$. Both the probabilistic solution (using Poisson distribution + CLT) and the solution using integral show this. My solution is also based on this kind of observation.
– Sangchul Lee
Nov 18 '18 at 19:16
Previous times this question has been asked: math.stackexchange.com/questions/2603315/…, math.stackexchange.com/questions/160248/… . I'm not flagging as duplicate because the question specifically asks for basic methods.
– Michael Lugo
Nov 15 '18 at 23:42
Previous times this question has been asked: math.stackexchange.com/questions/2603315/…, math.stackexchange.com/questions/160248/… . I'm not flagging as duplicate because the question specifically asks for basic methods.
– Michael Lugo
Nov 15 '18 at 23:42
Interestingly, the general term $n^k/k!$ is maximum when $k=n$. And by some magic, the sum "before" equals the sum "after" (asymptotically).
– Yves Daoust
Nov 18 '18 at 13:12
Interestingly, the general term $n^k/k!$ is maximum when $k=n$. And by some magic, the sum "before" equals the sum "after" (asymptotically).
– Yves Daoust
Nov 18 '18 at 13:12
2
2
Without an algebraic miracle, I do not think there is a simple and rigorous solution. My rationale is that any solution should demonstrate the understanding on the concentration behavior of the function $k mapsto frac{n^k}{k!}e^{-n}$ around $k = n$. Both the probabilistic solution (using Poisson distribution + CLT) and the solution using integral show this. My solution is also based on this kind of observation.
– Sangchul Lee
Nov 18 '18 at 19:16
Without an algebraic miracle, I do not think there is a simple and rigorous solution. My rationale is that any solution should demonstrate the understanding on the concentration behavior of the function $k mapsto frac{n^k}{k!}e^{-n}$ around $k = n$. Both the probabilistic solution (using Poisson distribution + CLT) and the solution using integral show this. My solution is also based on this kind of observation.
– Sangchul Lee
Nov 18 '18 at 19:16
add a comment |
1 Answer
1
active
oldest
votes
Table of Content.
- Heuristic argument
- Elementary proof, version 1.
- Elementary proof, version 2. (NEW!)
1. Heuristic argument.
Although far from being rigorous, one can provide a heuristic computation which explains why we expect the answer to be $frac{1}{2}$. Notice that
$$ frac{n^{n+j}/(n+j)!}{n^n / n!} = begin{cases}
prod_{k=1}^{j} frac{n}{n+k}, & j geq 1 \
1, & j = 0, -1 \
prod_{k=1}^{-j-1} frac{n-k}{n}, & j leq -2
end{cases}
$$
In any of cases, taking logarithm and applying the approximation $log(1+x) approx x$ shows that the above quantity is approximately $e^{-j^2/2n}$. So
$$
e^{-n} sum_{k=0}^{n} frac{n^k}{k!}
= frac{sum_{j=-n}^{0} frac{n!}{n^n sqrt{n}} frac{n^{n+j}}{(n+j)!} }{sum_{j=-n}^{infty} frac{n!}{n^n sqrt{n}}frac{n^{n+j}}{(n+j)!} }
approx frac{sum_{j=-n}^{0} e^{-(j/sqrt{n})^2/2} frac{1}{sqrt{n}} }{sum_{j=-n}^{infty} e^{-(j/sqrt{n})^2/2} frac{1}{sqrt{n}} }
approx frac{int_{-infty}^{0} e^{-x^2/2} , dx}{int_{-infty}^{infty} e^{-x^2/2} , dx}
= frac{1}{2}.
$$
Most of the solutions that I know is more or less a rigorous realization of this kind of observation, and so, it is either involved or requiring extra knowledge.
2. Elementary proof, version 1.
Define $A_n$, $B_n$ and $C_n$ by
$$ A_n := e^{-n} sum_{k=0}^{n} frac{n^k}{k!}, qquad B_n := e^{-n} sum_{k=n+1}^{infty} frac{n^k}{k!}, qquad C_n = frac{n^{n} e^{-n}}{n!}. $$
From the Taylor expansion of the exponential function, we know that $A_n + B_n = 1$. In order to show the desired convergence, it suffices to show that the following claim holds.
Claim. $A_n/B_n to 1$ as $ntoinfty$.
Indeed, once this is proved, then both $A_n$ and $B_n$ converge to $frac{1}{2}$ as $ntoinfty$.
Proof of Claim. Using the substitution $k = n-j$ followed by $p = j-1$, one may write
begin{align*}
frac{A_n}{C_n}
&= sum_{j=0}^{n} frac{n!}{(n-j)!n^j}
= 2 + sum_{p=1}^{n-1} prod_{l=1}^{p} left( 1 - frac{l}{n} right).
end{align*}
Similarly, applying the substitution $k = n+p$, one may write
begin{align*}
frac{B_n}{C_n}
&= sum_{p=1}^{infty} frac{n!n^p}{(n+p)!}
= sum_{p=1}^{infty} prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right).
end{align*}
1. Estimation of leading sums. Fix $alpha in left( 0, frac{1}{3} right)$ and set $N = N(alpha) = leftlceil n^{(1+alpha)/2} rightrceil$. Then using the asymptotic formula $1+x = e^{x+mathcal{O}(x^2)}$ as $x to 0$, for $1 leq p leq N$ we have
$$ prod_{l=1}^{p} left( 1 - frac{l}{n} right)
= expleft{ -frac{p^2}{2n} + mathcal{O}left( n^{-(1-3alpha)/2} right) right}
= prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right). $$
In particular, there exists a constant $C > 0$, depending only on $alpha$, such that
$$ maxBigg{ prod_{l=1}^{N} left( 1 - frac{l}{n} right), prod_{l=1}^{N} left( frac{1}{1 + frac{l}{n}} right) Bigg} leq C e^{-frac{1}{2}n^{alpha}}. $$
2. Estimation of tail sums. In this time, consider $p > N$. Then we have
$$ prod_{l=1}^{p} left( 1 - frac{l}{n} right)
leq C e^{-frac{1}{2}n^{alpha}} left( 1 - frac{N}{n} right)^{p-N}
quad text{and} quad
prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right)
leq C e^{-frac{1}{2}n^{alpha}} left( frac{1}{1 + frac{N}{n}} right)^{p-N}. $$
So the tail sum for $A_n/C_n$ can be bounded from above by
$$ sum_{p=N+1}^{n-1} prod_{l=1}^{p} left( 1 - frac{l}{n} right)
leq Ce^{-frac{1}{2}n^{alpha}} sum_{k = 0}^{infty} left( 1 - frac{N}{n} right)^k
leq frac{Cn}{N} e^{-frac{1}{2}n^{alpha}}
leq Cn^{(1-alpha)/2} e^{-frac{1}{2}n^{alpha}}, $$
and likewise,
$$ sum_{p=N+1}^{infty} prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right)
leq Ce^{-frac{1}{2}n^{alpha}} sum_{k = 0}^{infty} left( 1 - frac{N}{N+n} right)^k
leq frac{2Cn}{N} e^{-frac{1}{2}n^{alpha}}
leq 2Cn^{(1-alpha)/2} e^{-frac{1}{2}n^{alpha}}. $$
3. Conclusion. Combining altogether,
$$ frac{A_n}{B_n} = frac{left( 1 + o(1) right) sum_{p=1}^{N} e^{-frac{p^2}{2n}} + mathcal{O}(1)}{left( 1 + o(1) right) sum_{p=1}^{N} e^{-frac{p^2}{2n}} + o(1)}, $$
which can be easily shown to converge to $1$ as $ntoinfty$, since $sum_{p=1}^{N} e^{-frac{p^2}{2n}} geq sqrt{n} , e^{-1/2} to infty$ as $ntoinfty$. (In fact, this sum is $(1+o(1))sqrt{pi n/2}$ as $ntoinfty$.)
3. Elementary proof, version 2.
In this answer, we do appeal to the concentration behavior of the sum, but rather utilize a mysterious identity from combinatorics.
Write $A_n = e^{-n} sum_{k=0}^{n} frac{n^k}{k!}$ for the sequence of our interest. We also introduce the following auxiliary sequences:
$$
a_n = frac{n^n}{n!e^n}, qquad
b_n = (-1)^n binom{-1/2}{n} = frac{1}{4^n} binom{2n}{n},
$$
Before proceeding, we make some observations. The key ingredients are the following identities
$$ A_n = sum_{k=0}^{n} a_k a_{n-k}, qquad 1 = sum_{k=0}^{n} b_k b_{n-k}. $$
The former one is quite non-trivial, and a proof can be found here. On the other hand, the latter one is easily proved by comparing both sides of $
sum_{n=0}^{infty} x^n = frac{1}{1-x} = left( frac{1}{sqrt{1-x}} right)^2 = left( sum_{n=0}^{infty} b_n x^n right)^2$. Next, we have the following observation.
Lemma. $ frac{a_n}{b_n} to frac{1}{sqrt{2}} $ as $ntoinfty$.
This lemma tells that, roughly $a_{k}a_{n-k} approx frac{1}{2} b_k b_{n-k}$ and hence $ A_n approx frac{1}{2} sum_{k=0}^{n} b_k b_{n-k} = frac{1}{2}$. Indeed, this is an instance of the philosophy that `limit should be preserved under averaging', and so, it can be proved by a standard machinery. We separate the rigorous claim into a standalone result:
Proposition. Let $(a_n), (b_n)$ be sequences in $(0, infty)$ such that
$a_n/b_n to ell in (0, infty)$;
$b_n to 0$ as $ntoinfty$;
$sum_{k=0}^{n} b_k b_{n-k} = 1$ for all $n$.
Then $sum_{k=0}^{n} a_k a_{n-k} to ell^2$ as $ntoinfty$.
Therefore, $A_n to frac{1}{2}$ is a direct consequence of this proposition together with the well-known fact that $b_n to 0$. Indeed, this can be proved as follows:
$$ b_n^2
= left( frac{1 cdot 3 cdots (2n-1)}{2 cdot 4 cdots (2n)} right)^2
= left( frac{1 cdot 3}{2 cdot 2} right) left( frac{3 cdot 5}{4 cdot 4} right) cdots left( frac{(2n-3)(2n-1)}{(2n-2)(2n-2)} right) frac{2n-1}{4n^2}
leq frac{1}{2n}. $$
Finally, we prove the claims above.
Proof of Lemma. Using the identity $-int_{0}^{1} frac{u}{a+u} , du = a log (a+1) - a log a - 1$ for $a > 0$, we notice that
begin{align*}
&- sum_{k=1}^{n} int_{0}^{1} frac{u}{n+k-1+u} , du \
&= sum_{k=1}^{n} left[ (n+k-1)log (n+k) - (n+k-1)log(n+k-1) - 1 right] \
&= (2n)log(2n) - n log n - n - sum_{k=1}^{n} log(n+k) \
&= log left[ left( frac{4n}{e} right)^n frac{n!}{(2n)!} right]
= log left( frac{a_n}{b_n} right).
end{align*}
Then, using $ frac{1}{2(n+k)}
leq int_{0}^{1} frac{u}{n+k-1+u} , du
leq frac{1}{2(n+k-1)} $, we obtain
$$ -frac{1}{2}sum_{k=1}^{n} frac{1}{n+k-1}
leq log left( frac{a_n}{b_n} right)
leq -frac{1}{2}sum_{k=1}^{n} frac{1}{n+k}. $$
Therefore the conclusion follows from the well-known limit $ sum_{k=1}^{n} frac{1}{1+frac{k}{n}} frac{1}{n} to int_{0}^{1} frac{dx}{1+x} = log 2$.
Proof of Proposition. Let $alpha, beta $ satisfy $0 < alpha < ell < beta$. Then there exists $N$ such that $alpha leq frac{a_n}{b_n} leq beta$ for all $n geq N$. So, if $n geq 2N$, then
$$ alpha^2 sum_{k=N}^{n-N} b_k b_{n-k}
leq sum_{k=N}^{n-N} a_k a_{n-k}
leq beta^2 sum_{k=N}^{n-N} b_k b_{n-k}. $$
Now let $M > 0$ be a bound of $a_n/b_n$. Since $b_n to 0$ as $ntoinfty$, we have
$$ sum_{k=0}^{N-1} a_k a_{n-k} + sum_{k=n-N+1}^{n} a_k a_{n-k}
= 2sum_{k=0}^{N-1} a_k a_{n-k}
leq 2M^2 sum_{k=0}^{N-1} b_k b_{n-k}
xrightarrow[ntoinfty]{} 0 $$
Combining altogether and using $1 = sum_{k=0}^{n} b_k b_{n-k}$,
$$ alpha^2 leq liminf_{ntoinfty} sum_{k=0}^{n} a_k a_{n-k} leq limsup_{ntoinfty} sum_{k=0}^{n} a_k a_{n-k} leq beta^2. $$
Letting $alpha uparrow ell$ and $beta downarrow ell$ proves the desired identity.
We conclude with some remarks.
Remark. If we do not care about elementary solution, this approach can be simplified by showing that
$A_n$ is bounded and decreasing, hence converges.
By the identity $A_n = sum_{k=0}^{n} a_k a_{n-k}$, we have
$$ (1-x) sum_{n=0}^{infty} A_n x^n = left( frac{sum_{n=0}^{infty} a_n x^n}{sum_{n=0}^{infty} b_n x^n} right)^2, $$
hence by a version of abelian theorem, we obtain
$$ lim_{ntoinfty} A_n = lim_{ntoinfty} left( frac{a_n}{b_n} right)^2 = frac{1}{2}. $$
answered Nov 16 '18 at 2:30
Sangchul Lee
91.4k12163265
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%2f3000437%2flim-n-to-infty-e-n-sum-k-0n-fracnkk-frac12-basic-m%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Table of Content.
- Heuristic argument
- Elementary proof, version 1.
- Elementary proof, version 2. (NEW!)
1. Heuristic argument.
Although far from being rigorous, one can provide a heuristic computation which explains why we expect the answer to be $frac{1}{2}$. Notice that
$$ frac{n^{n+j}/(n+j)!}{n^n / n!} = begin{cases}
prod_{k=1}^{j} frac{n}{n+k}, & j geq 1 \
1, & j = 0, -1 \
prod_{k=1}^{-j-1} frac{n-k}{n}, & j leq -2
end{cases}
$$
In any of cases, taking logarithm and applying the approximation $log(1+x) approx x$ shows that the above quantity is approximately $e^{-j^2/2n}$. So
$$
e^{-n} sum_{k=0}^{n} frac{n^k}{k!}
= frac{sum_{j=-n}^{0} frac{n!}{n^n sqrt{n}} frac{n^{n+j}}{(n+j)!} }{sum_{j=-n}^{infty} frac{n!}{n^n sqrt{n}}frac{n^{n+j}}{(n+j)!} }
approx frac{sum_{j=-n}^{0} e^{-(j/sqrt{n})^2/2} frac{1}{sqrt{n}} }{sum_{j=-n}^{infty} e^{-(j/sqrt{n})^2/2} frac{1}{sqrt{n}} }
approx frac{int_{-infty}^{0} e^{-x^2/2} , dx}{int_{-infty}^{infty} e^{-x^2/2} , dx}
= frac{1}{2}.
$$
Most of the solutions that I know is more or less a rigorous realization of this kind of observation, and so, it is either involved or requiring extra knowledge.
2. Elementary proof, version 1.
Define $A_n$, $B_n$ and $C_n$ by
$$ A_n := e^{-n} sum_{k=0}^{n} frac{n^k}{k!}, qquad B_n := e^{-n} sum_{k=n+1}^{infty} frac{n^k}{k!}, qquad C_n = frac{n^{n} e^{-n}}{n!}. $$
From the Taylor expansion of the exponential function, we know that $A_n + B_n = 1$. In order to show the desired convergence, it suffices to show that the following claim holds.
Claim. $A_n/B_n to 1$ as $ntoinfty$.
Indeed, once this is proved, then both $A_n$ and $B_n$ converge to $frac{1}{2}$ as $ntoinfty$.
Proof of Claim. Using the substitution $k = n-j$ followed by $p = j-1$, one may write
begin{align*}
frac{A_n}{C_n}
&= sum_{j=0}^{n} frac{n!}{(n-j)!n^j}
= 2 + sum_{p=1}^{n-1} prod_{l=1}^{p} left( 1 - frac{l}{n} right).
end{align*}
Similarly, applying the substitution $k = n+p$, one may write
begin{align*}
frac{B_n}{C_n}
&= sum_{p=1}^{infty} frac{n!n^p}{(n+p)!}
= sum_{p=1}^{infty} prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right).
end{align*}
1. Estimation of leading sums. Fix $alpha in left( 0, frac{1}{3} right)$ and set $N = N(alpha) = leftlceil n^{(1+alpha)/2} rightrceil$. Then using the asymptotic formula $1+x = e^{x+mathcal{O}(x^2)}$ as $x to 0$, for $1 leq p leq N$ we have
$$ prod_{l=1}^{p} left( 1 - frac{l}{n} right)
= expleft{ -frac{p^2}{2n} + mathcal{O}left( n^{-(1-3alpha)/2} right) right}
= prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right). $$
In particular, there exists a constant $C > 0$, depending only on $alpha$, such that
$$ maxBigg{ prod_{l=1}^{N} left( 1 - frac{l}{n} right), prod_{l=1}^{N} left( frac{1}{1 + frac{l}{n}} right) Bigg} leq C e^{-frac{1}{2}n^{alpha}}. $$
2. Estimation of tail sums. In this time, consider $p > N$. Then we have
$$ prod_{l=1}^{p} left( 1 - frac{l}{n} right)
leq C e^{-frac{1}{2}n^{alpha}} left( 1 - frac{N}{n} right)^{p-N}
quad text{and} quad
prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right)
leq C e^{-frac{1}{2}n^{alpha}} left( frac{1}{1 + frac{N}{n}} right)^{p-N}. $$
So the tail sum for $A_n/C_n$ can be bounded from above by
$$ sum_{p=N+1}^{n-1} prod_{l=1}^{p} left( 1 - frac{l}{n} right)
leq Ce^{-frac{1}{2}n^{alpha}} sum_{k = 0}^{infty} left( 1 - frac{N}{n} right)^k
leq frac{Cn}{N} e^{-frac{1}{2}n^{alpha}}
leq Cn^{(1-alpha)/2} e^{-frac{1}{2}n^{alpha}}, $$
and likewise,
$$ sum_{p=N+1}^{infty} prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right)
leq Ce^{-frac{1}{2}n^{alpha}} sum_{k = 0}^{infty} left( 1 - frac{N}{N+n} right)^k
leq frac{2Cn}{N} e^{-frac{1}{2}n^{alpha}}
leq 2Cn^{(1-alpha)/2} e^{-frac{1}{2}n^{alpha}}. $$
3. Conclusion. Combining altogether,
$$ frac{A_n}{B_n} = frac{left( 1 + o(1) right) sum_{p=1}^{N} e^{-frac{p^2}{2n}} + mathcal{O}(1)}{left( 1 + o(1) right) sum_{p=1}^{N} e^{-frac{p^2}{2n}} + o(1)}, $$
which can be easily shown to converge to $1$ as $ntoinfty$, since $sum_{p=1}^{N} e^{-frac{p^2}{2n}} geq sqrt{n} , e^{-1/2} to infty$ as $ntoinfty$. (In fact, this sum is $(1+o(1))sqrt{pi n/2}$ as $ntoinfty$.)
3. Elementary proof, version 2.
In this answer, we do appeal to the concentration behavior of the sum, but rather utilize a mysterious identity from combinatorics.
Write $A_n = e^{-n} sum_{k=0}^{n} frac{n^k}{k!}$ for the sequence of our interest. We also introduce the following auxiliary sequences:
$$
a_n = frac{n^n}{n!e^n}, qquad
b_n = (-1)^n binom{-1/2}{n} = frac{1}{4^n} binom{2n}{n},
$$
Before proceeding, we make some observations. The key ingredients are the following identities
$$ A_n = sum_{k=0}^{n} a_k a_{n-k}, qquad 1 = sum_{k=0}^{n} b_k b_{n-k}. $$
The former one is quite non-trivial, and a proof can be found here. On the other hand, the latter one is easily proved by comparing both sides of $
sum_{n=0}^{infty} x^n = frac{1}{1-x} = left( frac{1}{sqrt{1-x}} right)^2 = left( sum_{n=0}^{infty} b_n x^n right)^2$. Next, we have the following observation.
Lemma. $ frac{a_n}{b_n} to frac{1}{sqrt{2}} $ as $ntoinfty$.
This lemma tells that, roughly $a_{k}a_{n-k} approx frac{1}{2} b_k b_{n-k}$ and hence $ A_n approx frac{1}{2} sum_{k=0}^{n} b_k b_{n-k} = frac{1}{2}$. Indeed, this is an instance of the philosophy that `limit should be preserved under averaging', and so, it can be proved by a standard machinery. We separate the rigorous claim into a standalone result:
Proposition. Let $(a_n), (b_n)$ be sequences in $(0, infty)$ such that
$a_n/b_n to ell in (0, infty)$;
$b_n to 0$ as $ntoinfty$;
$sum_{k=0}^{n} b_k b_{n-k} = 1$ for all $n$.
Then $sum_{k=0}^{n} a_k a_{n-k} to ell^2$ as $ntoinfty$.
Therefore, $A_n to frac{1}{2}$ is a direct consequence of this proposition together with the well-known fact that $b_n to 0$. Indeed, this can be proved as follows:
$$ b_n^2
= left( frac{1 cdot 3 cdots (2n-1)}{2 cdot 4 cdots (2n)} right)^2
= left( frac{1 cdot 3}{2 cdot 2} right) left( frac{3 cdot 5}{4 cdot 4} right) cdots left( frac{(2n-3)(2n-1)}{(2n-2)(2n-2)} right) frac{2n-1}{4n^2}
leq frac{1}{2n}. $$
Finally, we prove the claims above.
Proof of Lemma. Using the identity $-int_{0}^{1} frac{u}{a+u} , du = a log (a+1) - a log a - 1$ for $a > 0$, we notice that
begin{align*}
&- sum_{k=1}^{n} int_{0}^{1} frac{u}{n+k-1+u} , du \
&= sum_{k=1}^{n} left[ (n+k-1)log (n+k) - (n+k-1)log(n+k-1) - 1 right] \
&= (2n)log(2n) - n log n - n - sum_{k=1}^{n} log(n+k) \
&= log left[ left( frac{4n}{e} right)^n frac{n!}{(2n)!} right]
= log left( frac{a_n}{b_n} right).
end{align*}
Then, using $ frac{1}{2(n+k)}
leq int_{0}^{1} frac{u}{n+k-1+u} , du
leq frac{1}{2(n+k-1)} $, we obtain
$$ -frac{1}{2}sum_{k=1}^{n} frac{1}{n+k-1}
leq log left( frac{a_n}{b_n} right)
leq -frac{1}{2}sum_{k=1}^{n} frac{1}{n+k}. $$
Therefore the conclusion follows from the well-known limit $ sum_{k=1}^{n} frac{1}{1+frac{k}{n}} frac{1}{n} to int_{0}^{1} frac{dx}{1+x} = log 2$.
Proof of Proposition. Let $alpha, beta $ satisfy $0 < alpha < ell < beta$. Then there exists $N$ such that $alpha leq frac{a_n}{b_n} leq beta$ for all $n geq N$. So, if $n geq 2N$, then
$$ alpha^2 sum_{k=N}^{n-N} b_k b_{n-k}
leq sum_{k=N}^{n-N} a_k a_{n-k}
leq beta^2 sum_{k=N}^{n-N} b_k b_{n-k}. $$
Now let $M > 0$ be a bound of $a_n/b_n$. Since $b_n to 0$ as $ntoinfty$, we have
$$ sum_{k=0}^{N-1} a_k a_{n-k} + sum_{k=n-N+1}^{n} a_k a_{n-k}
= 2sum_{k=0}^{N-1} a_k a_{n-k}
leq 2M^2 sum_{k=0}^{N-1} b_k b_{n-k}
xrightarrow[ntoinfty]{} 0 $$
Combining altogether and using $1 = sum_{k=0}^{n} b_k b_{n-k}$,
$$ alpha^2 leq liminf_{ntoinfty} sum_{k=0}^{n} a_k a_{n-k} leq limsup_{ntoinfty} sum_{k=0}^{n} a_k a_{n-k} leq beta^2. $$
Letting $alpha uparrow ell$ and $beta downarrow ell$ proves the desired identity.
We conclude with some remarks.
Remark. If we do not care about elementary solution, this approach can be simplified by showing that
$A_n$ is bounded and decreasing, hence converges.
By the identity $A_n = sum_{k=0}^{n} a_k a_{n-k}$, we have
$$ (1-x) sum_{n=0}^{infty} A_n x^n = left( frac{sum_{n=0}^{infty} a_n x^n}{sum_{n=0}^{infty} b_n x^n} right)^2, $$
hence by a version of abelian theorem, we obtain
$$ lim_{ntoinfty} A_n = lim_{ntoinfty} left( frac{a_n}{b_n} right)^2 = frac{1}{2}. $$
answered Nov 16 '18 at 2:30
Sangchul Lee
91.4k12163265
add a comment |
Table of Content.
- Heuristic argument
- Elementary proof, version 1.
- Elementary proof, version 2. (NEW!)
1. Heuristic argument.
Although far from being rigorous, one can provide a heuristic computation which explains why we expect the answer to be $frac{1}{2}$. Notice that
$$ frac{n^{n+j}/(n+j)!}{n^n / n!} = begin{cases}
prod_{k=1}^{j} frac{n}{n+k}, & j geq 1 \
1, & j = 0, -1 \
prod_{k=1}^{-j-1} frac{n-k}{n}, & j leq -2
end{cases}
$$
In any of cases, taking logarithm and applying the approximation $log(1+x) approx x$ shows that the above quantity is approximately $e^{-j^2/2n}$. So
$$
e^{-n} sum_{k=0}^{n} frac{n^k}{k!}
= frac{sum_{j=-n}^{0} frac{n!}{n^n sqrt{n}} frac{n^{n+j}}{(n+j)!} }{sum_{j=-n}^{infty} frac{n!}{n^n sqrt{n}}frac{n^{n+j}}{(n+j)!} }
approx frac{sum_{j=-n}^{0} e^{-(j/sqrt{n})^2/2} frac{1}{sqrt{n}} }{sum_{j=-n}^{infty} e^{-(j/sqrt{n})^2/2} frac{1}{sqrt{n}} }
approx frac{int_{-infty}^{0} e^{-x^2/2} , dx}{int_{-infty}^{infty} e^{-x^2/2} , dx}
= frac{1}{2}.
$$
Most of the solutions that I know is more or less a rigorous realization of this kind of observation, and so, it is either involved or requiring extra knowledge.
2. Elementary proof, version 1.
Define $A_n$, $B_n$ and $C_n$ by
$$ A_n := e^{-n} sum_{k=0}^{n} frac{n^k}{k!}, qquad B_n := e^{-n} sum_{k=n+1}^{infty} frac{n^k}{k!}, qquad C_n = frac{n^{n} e^{-n}}{n!}. $$
From the Taylor expansion of the exponential function, we know that $A_n + B_n = 1$. In order to show the desired convergence, it suffices to show that the following claim holds.
Claim. $A_n/B_n to 1$ as $ntoinfty$.
Indeed, once this is proved, then both $A_n$ and $B_n$ converge to $frac{1}{2}$ as $ntoinfty$.
Proof of Claim. Using the substitution $k = n-j$ followed by $p = j-1$, one may write
begin{align*}
frac{A_n}{C_n}
&= sum_{j=0}^{n} frac{n!}{(n-j)!n^j}
= 2 + sum_{p=1}^{n-1} prod_{l=1}^{p} left( 1 - frac{l}{n} right).
end{align*}
Similarly, applying the substitution $k = n+p$, one may write
begin{align*}
frac{B_n}{C_n}
&= sum_{p=1}^{infty} frac{n!n^p}{(n+p)!}
= sum_{p=1}^{infty} prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right).
end{align*}
1. Estimation of leading sums. Fix $alpha in left( 0, frac{1}{3} right)$ and set $N = N(alpha) = leftlceil n^{(1+alpha)/2} rightrceil$. Then using the asymptotic formula $1+x = e^{x+mathcal{O}(x^2)}$ as $x to 0$, for $1 leq p leq N$ we have
$$ prod_{l=1}^{p} left( 1 - frac{l}{n} right)
= expleft{ -frac{p^2}{2n} + mathcal{O}left( n^{-(1-3alpha)/2} right) right}
= prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right). $$
In particular, there exists a constant $C > 0$, depending only on $alpha$, such that
$$ maxBigg{ prod_{l=1}^{N} left( 1 - frac{l}{n} right), prod_{l=1}^{N} left( frac{1}{1 + frac{l}{n}} right) Bigg} leq C e^{-frac{1}{2}n^{alpha}}. $$
2. Estimation of tail sums. In this time, consider $p > N$. Then we have
$$ prod_{l=1}^{p} left( 1 - frac{l}{n} right)
leq C e^{-frac{1}{2}n^{alpha}} left( 1 - frac{N}{n} right)^{p-N}
quad text{and} quad
prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right)
leq C e^{-frac{1}{2}n^{alpha}} left( frac{1}{1 + frac{N}{n}} right)^{p-N}. $$
So the tail sum for $A_n/C_n$ can be bounded from above by
$$ sum_{p=N+1}^{n-1} prod_{l=1}^{p} left( 1 - frac{l}{n} right)
leq Ce^{-frac{1}{2}n^{alpha}} sum_{k = 0}^{infty} left( 1 - frac{N}{n} right)^k
leq frac{Cn}{N} e^{-frac{1}{2}n^{alpha}}
leq Cn^{(1-alpha)/2} e^{-frac{1}{2}n^{alpha}}, $$
and likewise,
$$ sum_{p=N+1}^{infty} prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right)
leq Ce^{-frac{1}{2}n^{alpha}} sum_{k = 0}^{infty} left( 1 - frac{N}{N+n} right)^k
leq frac{2Cn}{N} e^{-frac{1}{2}n^{alpha}}
leq 2Cn^{(1-alpha)/2} e^{-frac{1}{2}n^{alpha}}. $$
3. Conclusion. Combining altogether,
$$ frac{A_n}{B_n} = frac{left( 1 + o(1) right) sum_{p=1}^{N} e^{-frac{p^2}{2n}} + mathcal{O}(1)}{left( 1 + o(1) right) sum_{p=1}^{N} e^{-frac{p^2}{2n}} + o(1)}, $$
which can be easily shown to converge to $1$ as $ntoinfty$, since $sum_{p=1}^{N} e^{-frac{p^2}{2n}} geq sqrt{n} , e^{-1/2} to infty$ as $ntoinfty$. (In fact, this sum is $(1+o(1))sqrt{pi n/2}$ as $ntoinfty$.)
3. Elementary proof, version 2.
In this answer, we do appeal to the concentration behavior of the sum, but rather utilize a mysterious identity from combinatorics.
Write $A_n = e^{-n} sum_{k=0}^{n} frac{n^k}{k!}$ for the sequence of our interest. We also introduce the following auxiliary sequences:
$$
a_n = frac{n^n}{n!e^n}, qquad
b_n = (-1)^n binom{-1/2}{n} = frac{1}{4^n} binom{2n}{n},
$$
Before proceeding, we make some observations. The key ingredients are the following identities
$$ A_n = sum_{k=0}^{n} a_k a_{n-k}, qquad 1 = sum_{k=0}^{n} b_k b_{n-k}. $$
The former one is quite non-trivial, and a proof can be found here. On the other hand, the latter one is easily proved by comparing both sides of $
sum_{n=0}^{infty} x^n = frac{1}{1-x} = left( frac{1}{sqrt{1-x}} right)^2 = left( sum_{n=0}^{infty} b_n x^n right)^2$. Next, we have the following observation.
Lemma. $ frac{a_n}{b_n} to frac{1}{sqrt{2}} $ as $ntoinfty$.
This lemma tells that, roughly $a_{k}a_{n-k} approx frac{1}{2} b_k b_{n-k}$ and hence $ A_n approx frac{1}{2} sum_{k=0}^{n} b_k b_{n-k} = frac{1}{2}$. Indeed, this is an instance of the philosophy that `limit should be preserved under averaging', and so, it can be proved by a standard machinery. We separate the rigorous claim into a standalone result:
Proposition. Let $(a_n), (b_n)$ be sequences in $(0, infty)$ such that
$a_n/b_n to ell in (0, infty)$;
$b_n to 0$ as $ntoinfty$;
$sum_{k=0}^{n} b_k b_{n-k} = 1$ for all $n$.
Then $sum_{k=0}^{n} a_k a_{n-k} to ell^2$ as $ntoinfty$.
Therefore, $A_n to frac{1}{2}$ is a direct consequence of this proposition together with the well-known fact that $b_n to 0$. Indeed, this can be proved as follows:
$$ b_n^2
= left( frac{1 cdot 3 cdots (2n-1)}{2 cdot 4 cdots (2n)} right)^2
= left( frac{1 cdot 3}{2 cdot 2} right) left( frac{3 cdot 5}{4 cdot 4} right) cdots left( frac{(2n-3)(2n-1)}{(2n-2)(2n-2)} right) frac{2n-1}{4n^2}
leq frac{1}{2n}. $$
Finally, we prove the claims above.
Proof of Lemma. Using the identity $-int_{0}^{1} frac{u}{a+u} , du = a log (a+1) - a log a - 1$ for $a > 0$, we notice that
begin{align*}
&- sum_{k=1}^{n} int_{0}^{1} frac{u}{n+k-1+u} , du \
&= sum_{k=1}^{n} left[ (n+k-1)log (n+k) - (n+k-1)log(n+k-1) - 1 right] \
&= (2n)log(2n) - n log n - n - sum_{k=1}^{n} log(n+k) \
&= log left[ left( frac{4n}{e} right)^n frac{n!}{(2n)!} right]
= log left( frac{a_n}{b_n} right).
end{align*}
Then, using $ frac{1}{2(n+k)}
leq int_{0}^{1} frac{u}{n+k-1+u} , du
leq frac{1}{2(n+k-1)} $, we obtain
$$ -frac{1}{2}sum_{k=1}^{n} frac{1}{n+k-1}
leq log left( frac{a_n}{b_n} right)
leq -frac{1}{2}sum_{k=1}^{n} frac{1}{n+k}. $$
Therefore the conclusion follows from the well-known limit $ sum_{k=1}^{n} frac{1}{1+frac{k}{n}} frac{1}{n} to int_{0}^{1} frac{dx}{1+x} = log 2$.
Proof of Proposition. Let $alpha, beta $ satisfy $0 < alpha < ell < beta$. Then there exists $N$ such that $alpha leq frac{a_n}{b_n} leq beta$ for all $n geq N$. So, if $n geq 2N$, then
$$ alpha^2 sum_{k=N}^{n-N} b_k b_{n-k}
leq sum_{k=N}^{n-N} a_k a_{n-k}
leq beta^2 sum_{k=N}^{n-N} b_k b_{n-k}. $$
Now let $M > 0$ be a bound of $a_n/b_n$. Since $b_n to 0$ as $ntoinfty$, we have
$$ sum_{k=0}^{N-1} a_k a_{n-k} + sum_{k=n-N+1}^{n} a_k a_{n-k}
= 2sum_{k=0}^{N-1} a_k a_{n-k}
leq 2M^2 sum_{k=0}^{N-1} b_k b_{n-k}
xrightarrow[ntoinfty]{} 0 $$
Combining altogether and using $1 = sum_{k=0}^{n} b_k b_{n-k}$,
$$ alpha^2 leq liminf_{ntoinfty} sum_{k=0}^{n} a_k a_{n-k} leq limsup_{ntoinfty} sum_{k=0}^{n} a_k a_{n-k} leq beta^2. $$
Letting $alpha uparrow ell$ and $beta downarrow ell$ proves the desired identity.
We conclude with some remarks.
Remark. If we do not care about elementary solution, this approach can be simplified by showing that
$A_n$ is bounded and decreasing, hence converges.
By the identity $A_n = sum_{k=0}^{n} a_k a_{n-k}$, we have
$$ (1-x) sum_{n=0}^{infty} A_n x^n = left( frac{sum_{n=0}^{infty} a_n x^n}{sum_{n=0}^{infty} b_n x^n} right)^2, $$
hence by a version of abelian theorem, we obtain
$$ lim_{ntoinfty} A_n = lim_{ntoinfty} left( frac{a_n}{b_n} right)^2 = frac{1}{2}. $$
answered Nov 16 '18 at 2:30
Sangchul Lee
91.4k12163265
add a comment |
Table of Content.
- Heuristic argument
- Elementary proof, version 1.
- Elementary proof, version 2. (NEW!)
1. Heuristic argument.
Although far from being rigorous, one can provide a heuristic computation which explains why we expect the answer to be $frac{1}{2}$. Notice that
$$ frac{n^{n+j}/(n+j)!}{n^n / n!} = begin{cases}
prod_{k=1}^{j} frac{n}{n+k}, & j geq 1 \
1, & j = 0, -1 \
prod_{k=1}^{-j-1} frac{n-k}{n}, & j leq -2
end{cases}
$$
In any of cases, taking logarithm and applying the approximation $log(1+x) approx x$ shows that the above quantity is approximately $e^{-j^2/2n}$. So
$$
e^{-n} sum_{k=0}^{n} frac{n^k}{k!}
= frac{sum_{j=-n}^{0} frac{n!}{n^n sqrt{n}} frac{n^{n+j}}{(n+j)!} }{sum_{j=-n}^{infty} frac{n!}{n^n sqrt{n}}frac{n^{n+j}}{(n+j)!} }
approx frac{sum_{j=-n}^{0} e^{-(j/sqrt{n})^2/2} frac{1}{sqrt{n}} }{sum_{j=-n}^{infty} e^{-(j/sqrt{n})^2/2} frac{1}{sqrt{n}} }
approx frac{int_{-infty}^{0} e^{-x^2/2} , dx}{int_{-infty}^{infty} e^{-x^2/2} , dx}
= frac{1}{2}.
$$
Most of the solutions that I know is more or less a rigorous realization of this kind of observation, and so, it is either involved or requiring extra knowledge.
2. Elementary proof, version 1.
Define $A_n$, $B_n$ and $C_n$ by
$$ A_n := e^{-n} sum_{k=0}^{n} frac{n^k}{k!}, qquad B_n := e^{-n} sum_{k=n+1}^{infty} frac{n^k}{k!}, qquad C_n = frac{n^{n} e^{-n}}{n!}. $$
From the Taylor expansion of the exponential function, we know that $A_n + B_n = 1$. In order to show the desired convergence, it suffices to show that the following claim holds.
Claim. $A_n/B_n to 1$ as $ntoinfty$.
Indeed, once this is proved, then both $A_n$ and $B_n$ converge to $frac{1}{2}$ as $ntoinfty$.
Proof of Claim. Using the substitution $k = n-j$ followed by $p = j-1$, one may write
begin{align*}
frac{A_n}{C_n}
&= sum_{j=0}^{n} frac{n!}{(n-j)!n^j}
= 2 + sum_{p=1}^{n-1} prod_{l=1}^{p} left( 1 - frac{l}{n} right).
end{align*}
Similarly, applying the substitution $k = n+p$, one may write
begin{align*}
frac{B_n}{C_n}
&= sum_{p=1}^{infty} frac{n!n^p}{(n+p)!}
= sum_{p=1}^{infty} prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right).
end{align*}
1. Estimation of leading sums. Fix $alpha in left( 0, frac{1}{3} right)$ and set $N = N(alpha) = leftlceil n^{(1+alpha)/2} rightrceil$. Then using the asymptotic formula $1+x = e^{x+mathcal{O}(x^2)}$ as $x to 0$, for $1 leq p leq N$ we have
$$ prod_{l=1}^{p} left( 1 - frac{l}{n} right)
= expleft{ -frac{p^2}{2n} + mathcal{O}left( n^{-(1-3alpha)/2} right) right}
= prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right). $$
In particular, there exists a constant $C > 0$, depending only on $alpha$, such that
$$ maxBigg{ prod_{l=1}^{N} left( 1 - frac{l}{n} right), prod_{l=1}^{N} left( frac{1}{1 + frac{l}{n}} right) Bigg} leq C e^{-frac{1}{2}n^{alpha}}. $$
2. Estimation of tail sums. In this time, consider $p > N$. Then we have
$$ prod_{l=1}^{p} left( 1 - frac{l}{n} right)
leq C e^{-frac{1}{2}n^{alpha}} left( 1 - frac{N}{n} right)^{p-N}
quad text{and} quad
prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right)
leq C e^{-frac{1}{2}n^{alpha}} left( frac{1}{1 + frac{N}{n}} right)^{p-N}. $$
So the tail sum for $A_n/C_n$ can be bounded from above by
$$ sum_{p=N+1}^{n-1} prod_{l=1}^{p} left( 1 - frac{l}{n} right)
leq Ce^{-frac{1}{2}n^{alpha}} sum_{k = 0}^{infty} left( 1 - frac{N}{n} right)^k
leq frac{Cn}{N} e^{-frac{1}{2}n^{alpha}}
leq Cn^{(1-alpha)/2} e^{-frac{1}{2}n^{alpha}}, $$
and likewise,
$$ sum_{p=N+1}^{infty} prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right)
leq Ce^{-frac{1}{2}n^{alpha}} sum_{k = 0}^{infty} left( 1 - frac{N}{N+n} right)^k
leq frac{2Cn}{N} e^{-frac{1}{2}n^{alpha}}
leq 2Cn^{(1-alpha)/2} e^{-frac{1}{2}n^{alpha}}. $$
3. Conclusion. Combining altogether,
$$ frac{A_n}{B_n} = frac{left( 1 + o(1) right) sum_{p=1}^{N} e^{-frac{p^2}{2n}} + mathcal{O}(1)}{left( 1 + o(1) right) sum_{p=1}^{N} e^{-frac{p^2}{2n}} + o(1)}, $$
which can be easily shown to converge to $1$ as $ntoinfty$, since $sum_{p=1}^{N} e^{-frac{p^2}{2n}} geq sqrt{n} , e^{-1/2} to infty$ as $ntoinfty$. (In fact, this sum is $(1+o(1))sqrt{pi n/2}$ as $ntoinfty$.)
3. Elementary proof, version 2.
In this answer, we do appeal to the concentration behavior of the sum, but rather utilize a mysterious identity from combinatorics.
Write $A_n = e^{-n} sum_{k=0}^{n} frac{n^k}{k!}$ for the sequence of our interest. We also introduce the following auxiliary sequences:
$$
a_n = frac{n^n}{n!e^n}, qquad
b_n = (-1)^n binom{-1/2}{n} = frac{1}{4^n} binom{2n}{n},
$$
Before proceeding, we make some observations. The key ingredients are the following identities
$$ A_n = sum_{k=0}^{n} a_k a_{n-k}, qquad 1 = sum_{k=0}^{n} b_k b_{n-k}. $$
The former one is quite non-trivial, and a proof can be found here. On the other hand, the latter one is easily proved by comparing both sides of $
sum_{n=0}^{infty} x^n = frac{1}{1-x} = left( frac{1}{sqrt{1-x}} right)^2 = left( sum_{n=0}^{infty} b_n x^n right)^2$. Next, we have the following observation.
Lemma. $ frac{a_n}{b_n} to frac{1}{sqrt{2}} $ as $ntoinfty$.
This lemma tells that, roughly $a_{k}a_{n-k} approx frac{1}{2} b_k b_{n-k}$ and hence $ A_n approx frac{1}{2} sum_{k=0}^{n} b_k b_{n-k} = frac{1}{2}$. Indeed, this is an instance of the philosophy that `limit should be preserved under averaging', and so, it can be proved by a standard machinery. We separate the rigorous claim into a standalone result:
Proposition. Let $(a_n), (b_n)$ be sequences in $(0, infty)$ such that
$a_n/b_n to ell in (0, infty)$;
$b_n to 0$ as $ntoinfty$;
$sum_{k=0}^{n} b_k b_{n-k} = 1$ for all $n$.
Then $sum_{k=0}^{n} a_k a_{n-k} to ell^2$ as $ntoinfty$.
Therefore, $A_n to frac{1}{2}$ is a direct consequence of this proposition together with the well-known fact that $b_n to 0$. Indeed, this can be proved as follows:
$$ b_n^2
= left( frac{1 cdot 3 cdots (2n-1)}{2 cdot 4 cdots (2n)} right)^2
= left( frac{1 cdot 3}{2 cdot 2} right) left( frac{3 cdot 5}{4 cdot 4} right) cdots left( frac{(2n-3)(2n-1)}{(2n-2)(2n-2)} right) frac{2n-1}{4n^2}
leq frac{1}{2n}. $$
Finally, we prove the claims above.
Proof of Lemma. Using the identity $-int_{0}^{1} frac{u}{a+u} , du = a log (a+1) - a log a - 1$ for $a > 0$, we notice that
begin{align*}
&- sum_{k=1}^{n} int_{0}^{1} frac{u}{n+k-1+u} , du \
&= sum_{k=1}^{n} left[ (n+k-1)log (n+k) - (n+k-1)log(n+k-1) - 1 right] \
&= (2n)log(2n) - n log n - n - sum_{k=1}^{n} log(n+k) \
&= log left[ left( frac{4n}{e} right)^n frac{n!}{(2n)!} right]
= log left( frac{a_n}{b_n} right).
end{align*}
Then, using $ frac{1}{2(n+k)}
leq int_{0}^{1} frac{u}{n+k-1+u} , du
leq frac{1}{2(n+k-1)} $, we obtain
$$ -frac{1}{2}sum_{k=1}^{n} frac{1}{n+k-1}
leq log left( frac{a_n}{b_n} right)
leq -frac{1}{2}sum_{k=1}^{n} frac{1}{n+k}. $$
Therefore the conclusion follows from the well-known limit $ sum_{k=1}^{n} frac{1}{1+frac{k}{n}} frac{1}{n} to int_{0}^{1} frac{dx}{1+x} = log 2$.
Proof of Proposition. Let $alpha, beta $ satisfy $0 < alpha < ell < beta$. Then there exists $N$ such that $alpha leq frac{a_n}{b_n} leq beta$ for all $n geq N$. So, if $n geq 2N$, then
$$ alpha^2 sum_{k=N}^{n-N} b_k b_{n-k}
leq sum_{k=N}^{n-N} a_k a_{n-k}
leq beta^2 sum_{k=N}^{n-N} b_k b_{n-k}. $$
Now let $M > 0$ be a bound of $a_n/b_n$. Since $b_n to 0$ as $ntoinfty$, we have
$$ sum_{k=0}^{N-1} a_k a_{n-k} + sum_{k=n-N+1}^{n} a_k a_{n-k}
= 2sum_{k=0}^{N-1} a_k a_{n-k}
leq 2M^2 sum_{k=0}^{N-1} b_k b_{n-k}
xrightarrow[ntoinfty]{} 0 $$
Combining altogether and using $1 = sum_{k=0}^{n} b_k b_{n-k}$,
$$ alpha^2 leq liminf_{ntoinfty} sum_{k=0}^{n} a_k a_{n-k} leq limsup_{ntoinfty} sum_{k=0}^{n} a_k a_{n-k} leq beta^2. $$
Letting $alpha uparrow ell$ and $beta downarrow ell$ proves the desired identity.
We conclude with some remarks.
Remark. If we do not care about elementary solution, this approach can be simplified by showing that
$A_n$ is bounded and decreasing, hence converges.
By the identity $A_n = sum_{k=0}^{n} a_k a_{n-k}$, we have
$$ (1-x) sum_{n=0}^{infty} A_n x^n = left( frac{sum_{n=0}^{infty} a_n x^n}{sum_{n=0}^{infty} b_n x^n} right)^2, $$
hence by a version of abelian theorem, we obtain
$$ lim_{ntoinfty} A_n = lim_{ntoinfty} left( frac{a_n}{b_n} right)^2 = frac{1}{2}. $$
answered Nov 16 '18 at 2:30
Sangchul Lee
91.4k12163265
Table of Content.
- Heuristic argument
- Elementary proof, version 1.
- Elementary proof, version 2. (NEW!)
1. Heuristic argument.
Although far from being rigorous, one can provide a heuristic computation which explains why we expect the answer to be $frac{1}{2}$. Notice that
$$ frac{n^{n+j}/(n+j)!}{n^n / n!} = begin{cases}
prod_{k=1}^{j} frac{n}{n+k}, & j geq 1 \
1, & j = 0, -1 \
prod_{k=1}^{-j-1} frac{n-k}{n}, & j leq -2
end{cases}
$$
In any of cases, taking logarithm and applying the approximation $log(1+x) approx x$ shows that the above quantity is approximately $e^{-j^2/2n}$. So
$$
e^{-n} sum_{k=0}^{n} frac{n^k}{k!}
= frac{sum_{j=-n}^{0} frac{n!}{n^n sqrt{n}} frac{n^{n+j}}{(n+j)!} }{sum_{j=-n}^{infty} frac{n!}{n^n sqrt{n}}frac{n^{n+j}}{(n+j)!} }
approx frac{sum_{j=-n}^{0} e^{-(j/sqrt{n})^2/2} frac{1}{sqrt{n}} }{sum_{j=-n}^{infty} e^{-(j/sqrt{n})^2/2} frac{1}{sqrt{n}} }
approx frac{int_{-infty}^{0} e^{-x^2/2} , dx}{int_{-infty}^{infty} e^{-x^2/2} , dx}
= frac{1}{2}.
$$
Most of the solutions that I know is more or less a rigorous realization of this kind of observation, and so, it is either involved or requiring extra knowledge.
2. Elementary proof, version 1.
Define $A_n$, $B_n$ and $C_n$ by
$$ A_n := e^{-n} sum_{k=0}^{n} frac{n^k}{k!}, qquad B_n := e^{-n} sum_{k=n+1}^{infty} frac{n^k}{k!}, qquad C_n = frac{n^{n} e^{-n}}{n!}. $$
From the Taylor expansion of the exponential function, we know that $A_n + B_n = 1$. In order to show the desired convergence, it suffices to show that the following claim holds.
Claim. $A_n/B_n to 1$ as $ntoinfty$.
Indeed, once this is proved, then both $A_n$ and $B_n$ converge to $frac{1}{2}$ as $ntoinfty$.
Proof of Claim. Using the substitution $k = n-j$ followed by $p = j-1$, one may write
begin{align*}
frac{A_n}{C_n}
&= sum_{j=0}^{n} frac{n!}{(n-j)!n^j}
= 2 + sum_{p=1}^{n-1} prod_{l=1}^{p} left( 1 - frac{l}{n} right).
end{align*}
Similarly, applying the substitution $k = n+p$, one may write
begin{align*}
frac{B_n}{C_n}
&= sum_{p=1}^{infty} frac{n!n^p}{(n+p)!}
= sum_{p=1}^{infty} prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right).
end{align*}
1. Estimation of leading sums. Fix $alpha in left( 0, frac{1}{3} right)$ and set $N = N(alpha) = leftlceil n^{(1+alpha)/2} rightrceil$. Then using the asymptotic formula $1+x = e^{x+mathcal{O}(x^2)}$ as $x to 0$, for $1 leq p leq N$ we have
$$ prod_{l=1}^{p} left( 1 - frac{l}{n} right)
= expleft{ -frac{p^2}{2n} + mathcal{O}left( n^{-(1-3alpha)/2} right) right}
= prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right). $$
In particular, there exists a constant $C > 0$, depending only on $alpha$, such that
$$ maxBigg{ prod_{l=1}^{N} left( 1 - frac{l}{n} right), prod_{l=1}^{N} left( frac{1}{1 + frac{l}{n}} right) Bigg} leq C e^{-frac{1}{2}n^{alpha}}. $$
2. Estimation of tail sums. In this time, consider $p > N$. Then we have
$$ prod_{l=1}^{p} left( 1 - frac{l}{n} right)
leq C e^{-frac{1}{2}n^{alpha}} left( 1 - frac{N}{n} right)^{p-N}
quad text{and} quad
prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right)
leq C e^{-frac{1}{2}n^{alpha}} left( frac{1}{1 + frac{N}{n}} right)^{p-N}. $$
So the tail sum for $A_n/C_n$ can be bounded from above by
$$ sum_{p=N+1}^{n-1} prod_{l=1}^{p} left( 1 - frac{l}{n} right)
leq Ce^{-frac{1}{2}n^{alpha}} sum_{k = 0}^{infty} left( 1 - frac{N}{n} right)^k
leq frac{Cn}{N} e^{-frac{1}{2}n^{alpha}}
leq Cn^{(1-alpha)/2} e^{-frac{1}{2}n^{alpha}}, $$
and likewise,
$$ sum_{p=N+1}^{infty} prod_{l=1}^{p} left( frac{1}{1 + frac{l}{n}} right)
leq Ce^{-frac{1}{2}n^{alpha}} sum_{k = 0}^{infty} left( 1 - frac{N}{N+n} right)^k
leq frac{2Cn}{N} e^{-frac{1}{2}n^{alpha}}
leq 2Cn^{(1-alpha)/2} e^{-frac{1}{2}n^{alpha}}. $$
3. Conclusion. Combining altogether,
$$ frac{A_n}{B_n} = frac{left( 1 + o(1) right) sum_{p=1}^{N} e^{-frac{p^2}{2n}} + mathcal{O}(1)}{left( 1 + o(1) right) sum_{p=1}^{N} e^{-frac{p^2}{2n}} + o(1)}, $$
which can be easily shown to converge to $1$ as $ntoinfty$, since $sum_{p=1}^{N} e^{-frac{p^2}{2n}} geq sqrt{n} , e^{-1/2} to infty$ as $ntoinfty$. (In fact, this sum is $(1+o(1))sqrt{pi n/2}$ as $ntoinfty$.)
3. Elementary proof, version 2.
In this answer, we do appeal to the concentration behavior of the sum, but rather utilize a mysterious identity from combinatorics.
Write $A_n = e^{-n} sum_{k=0}^{n} frac{n^k}{k!}$ for the sequence of our interest. We also introduce the following auxiliary sequences:
$$
a_n = frac{n^n}{n!e^n}, qquad
b_n = (-1)^n binom{-1/2}{n} = frac{1}{4^n} binom{2n}{n},
$$
Before proceeding, we make some observations. The key ingredients are the following identities
$$ A_n = sum_{k=0}^{n} a_k a_{n-k}, qquad 1 = sum_{k=0}^{n} b_k b_{n-k}. $$
The former one is quite non-trivial, and a proof can be found here. On the other hand, the latter one is easily proved by comparing both sides of $
sum_{n=0}^{infty} x^n = frac{1}{1-x} = left( frac{1}{sqrt{1-x}} right)^2 = left( sum_{n=0}^{infty} b_n x^n right)^2$. Next, we have the following observation.
Lemma. $ frac{a_n}{b_n} to frac{1}{sqrt{2}} $ as $ntoinfty$.
This lemma tells that, roughly $a_{k}a_{n-k} approx frac{1}{2} b_k b_{n-k}$ and hence $ A_n approx frac{1}{2} sum_{k=0}^{n} b_k b_{n-k} = frac{1}{2}$. Indeed, this is an instance of the philosophy that `limit should be preserved under averaging', and so, it can be proved by a standard machinery. We separate the rigorous claim into a standalone result:
Proposition. Let $(a_n), (b_n)$ be sequences in $(0, infty)$ such that
$a_n/b_n to ell in (0, infty)$;
$b_n to 0$ as $ntoinfty$;
$sum_{k=0}^{n} b_k b_{n-k} = 1$ for all $n$.
Then $sum_{k=0}^{n} a_k a_{n-k} to ell^2$ as $ntoinfty$.
Therefore, $A_n to frac{1}{2}$ is a direct consequence of this proposition together with the well-known fact that $b_n to 0$. Indeed, this can be proved as follows:
$$ b_n^2
= left( frac{1 cdot 3 cdots (2n-1)}{2 cdot 4 cdots (2n)} right)^2
= left( frac{1 cdot 3}{2 cdot 2} right) left( frac{3 cdot 5}{4 cdot 4} right) cdots left( frac{(2n-3)(2n-1)}{(2n-2)(2n-2)} right) frac{2n-1}{4n^2}
leq frac{1}{2n}. $$
Finally, we prove the claims above.
Proof of Lemma. Using the identity $-int_{0}^{1} frac{u}{a+u} , du = a log (a+1) - a log a - 1$ for $a > 0$, we notice that
begin{align*}
&- sum_{k=1}^{n} int_{0}^{1} frac{u}{n+k-1+u} , du \
&= sum_{k=1}^{n} left[ (n+k-1)log (n+k) - (n+k-1)log(n+k-1) - 1 right] \
&= (2n)log(2n) - n log n - n - sum_{k=1}^{n} log(n+k) \
&= log left[ left( frac{4n}{e} right)^n frac{n!}{(2n)!} right]
= log left( frac{a_n}{b_n} right).
end{align*}
Then, using $ frac{1}{2(n+k)}
leq int_{0}^{1} frac{u}{n+k-1+u} , du
leq frac{1}{2(n+k-1)} $, we obtain
$$ -frac{1}{2}sum_{k=1}^{n} frac{1}{n+k-1}
leq log left( frac{a_n}{b_n} right)
leq -frac{1}{2}sum_{k=1}^{n} frac{1}{n+k}. $$
Therefore the conclusion follows from the well-known limit $ sum_{k=1}^{n} frac{1}{1+frac{k}{n}} frac{1}{n} to int_{0}^{1} frac{dx}{1+x} = log 2$.
Proof of Proposition. Let $alpha, beta $ satisfy $0 < alpha < ell < beta$. Then there exists $N$ such that $alpha leq frac{a_n}{b_n} leq beta$ for all $n geq N$. So, if $n geq 2N$, then
$$ alpha^2 sum_{k=N}^{n-N} b_k b_{n-k}
leq sum_{k=N}^{n-N} a_k a_{n-k}
leq beta^2 sum_{k=N}^{n-N} b_k b_{n-k}. $$
Now let $M > 0$ be a bound of $a_n/b_n$. Since $b_n to 0$ as $ntoinfty$, we have
$$ sum_{k=0}^{N-1} a_k a_{n-k} + sum_{k=n-N+1}^{n} a_k a_{n-k}
= 2sum_{k=0}^{N-1} a_k a_{n-k}
leq 2M^2 sum_{k=0}^{N-1} b_k b_{n-k}
xrightarrow[ntoinfty]{} 0 $$
Combining altogether and using $1 = sum_{k=0}^{n} b_k b_{n-k}$,
$$ alpha^2 leq liminf_{ntoinfty} sum_{k=0}^{n} a_k a_{n-k} leq limsup_{ntoinfty} sum_{k=0}^{n} a_k a_{n-k} leq beta^2. $$
Letting $alpha uparrow ell$ and $beta downarrow ell$ proves the desired identity.
We conclude with some remarks.
Remark. If we do not care about elementary solution, this approach can be simplified by showing that
$A_n$ is bounded and decreasing, hence converges.
By the identity $A_n = sum_{k=0}^{n} a_k a_{n-k}$, we have
$$ (1-x) sum_{n=0}^{infty} A_n x^n = left( frac{sum_{n=0}^{infty} a_n x^n}{sum_{n=0}^{infty} b_n x^n} right)^2, $$
hence by a version of abelian theorem, we obtain
$$ lim_{ntoinfty} A_n = lim_{ntoinfty} left( frac{a_n}{b_n} right)^2 = frac{1}{2}. $$
answered Nov 16 '18 at 2:30
Sangchul Lee
91.4k12163265
edited Nov 28 '18 at 21:12
answered Nov 16 '18 at 2:30
Sangchul Lee
91.4k12163265
answered Nov 16 '18 at 2:30
Sangchul Lee
91.4k12163265
answered Nov 16 '18 at 2:30
Sangchul Lee
91.4k12163265
91.4k12163265
add a comment |
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3000437%2flim-n-to-infty-e-n-sum-k-0n-fracnkk-frac12-basic-m%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
Previous times this question has been asked: math.stackexchange.com/questions/2603315/…, math.stackexchange.com/questions/160248/… . I'm not flagging as duplicate because the question specifically asks for basic methods.
– Michael Lugo
Nov 15 '18 at 23:42
Interestingly, the general term $n^k/k!$ is maximum when $k=n$. And by some magic, the sum "before" equals the sum "after" (asymptotically).
– Yves Daoust
Nov 18 '18 at 13:12
2
Without an algebraic miracle, I do not think there is a simple and rigorous solution. My rationale is that any solution should demonstrate the understanding on the concentration behavior of the function $k mapsto frac{n^k}{k!}e^{-n}$ around $k = n$. Both the probabilistic solution (using Poisson distribution + CLT) and the solution using integral show this. My solution is also based on this kind of observation.
– Sangchul Lee
Nov 18 '18 at 19:16