# Finding the asymptotic bound of a summation

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$?

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}$.

• Very nice! I did attempt to apply Stirling's formula as well, but the following calculus is the gold. Aug 9, 2017 at 9:30

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.
• 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. Aug 9, 2017 at 22:04
• @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. Aug 10, 2017 at 8:00 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}} + ...\$