2
$\begingroup$

Given a sufficiently large positive integer $n$, I would like to know the asymptotic bound in $n$ of the following summation: $$ \sum_{i=0}^{n}{\frac{P(n, i)}{n^i}} = \sum_{i=0}^{n}{\frac{n!}{(n-i)! \cdot n^i}.} $$

Is it $O(n)$, $O(\log n)$, $\dots$?

$\endgroup$

3 Answers 3

5
$\begingroup$

If you don't need very precise information, then the quick answer is that $n^{1/2}$ is about right.

I want to use Stirling's formula in the version $$ An^{n+1/2}e^{-n} \le n! \le Bn^{n+1/2}e^{-n} . $$ This shows that $$ \frac{n!}{(n-j)!n^j}\simeq e^{-j}\left( \frac{n}{n-j}\right)^{n-j+1/2} , $$ so the sum is $$ S(n) \simeq e^{-n}\sum_{k=1}^n \left( \frac{ne}{k}\right)^{k+1/2} . $$ By calculus, the function $f(x)=e^{-n}(ne/x)^{x+1/2}$ has a unique maximum on $1\le x\le n$ at $x=n-1/2+o(1)$. So for an upper bound, we can estimate the terms with $1\le k\le (1-\delta)n$ by taking $k=(1-\delta)n$ instead. Now $$ f((1-\delta)n) = \left( \frac{e^{-\delta}}{1-\delta}\right)^n \simeq e^{-\delta^2 n} , $$ so this produces the estimate $S(n)\lesssim \delta n + ne^{-\delta^2 n}$. With $\delta = C(\log n/n)^{1/2}$, this becomes $S(n)\lesssim (n\log n)^{1/2}$.

In the same way, we can use $\delta n f(n-\delta n)\gtrsim \delta n e^{-\delta^2 n}$ as a lower bound, and for $\delta = n^{-1/2}$, this gives that $S(n)\gtrsim n^{1/2}$.

$\endgroup$
1
  • $\begingroup$ Very nice! I did attempt to apply Stirling's formula as well, but the following calculus is the gold. $\endgroup$
    – Blue Bear
    Aug 9, 2017 at 9:30
3
$\begingroup$

(Edited after Christian's comments.)

For $0\le i\le n^{4/7}$, $$n!/(n-i)! = n^i \exp(-i(i-1)/(2n)+O(i^3/n^2)).$$ Approximate the sum for that range by the corresponding integral (a gaussian with the right endpoint far into the tail). This can be formally justified by the Euler-Maclaurin theorem, and probably by elementary reasoning as the integrand is decreasing.

Bound the remainder of the sum by $n$ times the largest (first) term. This gives the negligible contribution $e^{-\Omega(n^{1/7})}$.

We find that the sum is $$ \sqrt{\frac{\pi n}{2}} + O(1). $$ Confirmed numerically.

$\endgroup$
3
  • $\begingroup$ @ChristianRemling Yes, I was careless. Fixing now. $\endgroup$ Aug 9, 2017 at 21:31
  • $\begingroup$ Thanks. I still think you're not establishing the precise constant $\sqrt{\pi/2}$ with your theoretical argument since the $e^{O(i^3/n^2)}=e^{O(1)}$ can contribute to this. $\endgroup$ Aug 9, 2017 at 22:04
  • $\begingroup$ @ChristianRemling $i^3/n^2$ can be around a constant in the later part of the first range but there it is overwhelmed by the term $-i^2/(2n)$ and has negligible effect. However the argument might be clearer if the cut is made between $n^{1/2}$ and $n^{2/3}; I'll edit it like that. $\endgroup$ Aug 10, 2017 at 8:00
1
$\begingroup$

This is a well-studied problem. The sum can be written as $n^{-n}e^{n}\Gamma(1+n,n).$ Use a functional relationship for the incomplete gamma function and the asymptotic expansion found in, say, the Digital Library of Mathematical Functions, 8.11.12 to get

$\sum_{k=0}^{n}\binom{n}{k} \frac{k!}{n^k} \sim \sqrt{\frac{\pi n}{2}} + 2/3 + \frac{1}{24}\sqrt{\frac{2 \pi}{n}} + ...$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.