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$? 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!
 A: 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.
A: 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.
