How do I show that $\frac{1}{n}\sum_{k=1}^{n}\frac{n!}{(n-k)!n^{k}}$ converges to zero as $n\to\infty$?

Question

How do I show that $$\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^{n}\frac{n!}{(n-k)!n^{k}}=0?$$ I read that $\sum_{k=1}^{n}\frac{n!}{(n-k)!n^{k}}$ grows asymptotically like $\sqrt{\pi n/2}$. So from this, the result follows. However, I have no idea how to analyse the asympotic behaviour. Maybe there is a way to avoid it?

Any suggestions are greatly appreciated!

Answer 1

If you want to avoid tools like Stirling, here's one easy way: let's look at each summand. You have \begin{equation} \frac{n!}{(n-k)!n^k}=\frac{n}{n}\cdot \frac{n-1}{n}\cdot\ldots\cdot \frac{n-k+1}{n}=\prod_{i=1}^{k-1} \bigg(1-\frac{i}{n}\bigg). \end{equation} Using the easy inequality $1-x\leq e^{-x}$, this is at most \begin{equation} \prod_{i=1}^{k-1} \exp\bigg(-\frac{i}{n}\bigg)=\exp\bigg(\sum_{i=1}^{k-1} -i/n\bigg). \end{equation} Using standard expressions for sums of arithmetic series, this is $\exp(-\Theta(k^2/n))$ for any $k$. So for any $k\geq C\sqrt{n\ln n}$ for some absolute constant $C$, this is at most $1/\sqrt{n}$.

Now, breaking the sum into terms that are at most $C\sqrt{n\ln n}$ and those that are above this, the former are all at most $1$, while the latter are at most $1/\sqrt{n}$. Therefore, the contribution of the former terms is at most $O(\sqrt{n\ln n})$ (as there are that many terms and are all at most $1$), while the contribution of the latter terms is at most $O(\sqrt{n})$ (as there are at most $n$ such terms and they all contribute at most $1/\sqrt{n}$). As a result, the sum is $O(\sqrt{n \ln n})$, and so dividing by $n$ makes the total expression $O(\sqrt{\ln n/n})$, proving the limit is zero. This is off by your known estimate by a logarithmic factor, but uses no high-powered tools at all.

Answer 2

By using the Gaussian integral relation for the $\Gamma$-function, it is easily derived that $$\frac{1}{n} \sum_{k=0}^n \binom{n}{k} \frac{k!}{n^k} = \int_0^\infty e^{-n \, t}(1+t)^n \, dt $$ To get a rigorous asymptotic expansion, one writes $u=e^{-t}(1+t)$ and then uses properties about the Lambert-W function around a branch point. However, to keep it simple, notice that $(1+t)e^{-t} < \text{sech}(a\,t) $ for all $t>0$ for $a$ less than about 0.7655. Then the integral can be bounded as

$$\int_0^\infty e^{-n \, t}(1+t)^n \, dt < \int_0^\infty \text{sech}^n(a\,t)dt = \frac{1}{a} \int_0^\infty \text{sech}^n(t)dt$$ $$=\frac{\sqrt{\pi}}{2a}\frac{\Gamma(n/2)}{\Gamma(1/2+n/2)} \sim \frac{\sqrt{\pi}}{2a} n^{-1/2}.$$

It's now obvious that the limit will be zero.