Find a difficult limit How can you prove $\lim_{n \rightarrow \infty} n\sum_{i=1}^{n-1}\frac{i(n-2)!}{(n-1-i)!n^{i+1}} = 1$?  I know that $\sum_{i=1}^{n}\frac{i (n!)}{(n-i)!n^{i}} = n$ but I can't see how to get from one to the other.
 A: Let $X$ be a discrete random variable that follows Naor's distribution. Then its probability mass function is:
$$
   \mathbb{P}\left(X=m\right) = \frac{m}{n^m} \frac{(n-1)!}{(n-m)!} [ 1 \leqslant m \leqslant n ]
$$
Normalization condition entails $\sum_{m=1}^n \frac{m (n!)}{(n-m)! n^m} = n$. The Naor's distribution is also closely related to the distribution of the random number of uniform samples with replacement from set of $n$ distinct elements until the first repeat (e.g. see here).
Rewriting the limit as 
$$
   \lim_{n \rightarrow \infty} n\sum_{i=1}^{n-1}\frac{i(n-2)!}{(n-1-i)!n^{i+1}} = \lim_{n \rightarrow \infty} \sum_{i=1}^{n}\frac{i(n-1)!}{(n-i)!(n+1)^{i}}
$$
The sum in question can be recast as expectation:
$$
   \sum_{m=1}^{n}\frac{m (n-1)!}{(n-m)!(n+1)^{m}} = \mathbb{E}\left( \left(\frac{n}{n+1}\right)^X \right) = \mathbb{E}\left( \left(1-\frac{1}{n+1}\right)^X \right) \geqslant \left(1-\frac{1}{n+1}\right)^{\mathbb{E}(X)}
$$
where the last inequality follows by Jensen's inequality. We thus have:
$$
    1 > \mathbb{E}\left( \left(1-\frac{1}{n+1}\right)^X \right) \geqslant \left(1-\frac{1}{n+1}\right)^{\mathbb{E}(X)}
$$
The claims now follows should we establish that $\mathbb{E}(X)$ grows slower than $n$, i.e. $\mathbb{E}\left(X\right) \sim \mathcal{o}(n)$. The mean can be found in closed form in terms of incomplete $\Gamma$-function:
$$
  \mathbb{E}\left(X\right) = -1 + \left(\frac{\mathrm{e}}{n}\right)^n \Gamma\left(n+1, n\right)
$$
From here we borrow the result for the large $n$ asymptotics of the $\Gamma(n+1,n)$:
$$
  \mathbb{E}\left(X\right) = \sqrt{\frac{\pi}{2} \cdot n} - \frac{1}{3} + \mathcal{o}(1)
$$
Now by the squeeze theorem the large $n$ limit of interest follows.
A: Using what Sasha wrote in the comments we can evaluate the sum as follows:
$$\begin{eqnarray}
   \sum_{i=1}^{n-1} \frac{i}{n^i} \frac{(n-2)!}{(n-1-i)!} &\stackrel{i=n-1-k}{=}& \frac{(n-2)!}{n^{n-1}} \sum_{k=0}^{n-2} \left(n-1-k\right) \frac{n^k}{k!} 
= \frac{(n-2)!}{n^{n-1}} \sum_{k=0}^{n-1} \left(n-1-k\right) \frac{n^k}{k!} \\ 
&=& \frac{(n-1)!}{n^{n-1}} \sum_{k=0}^{n-1} \frac{n^k}{k!} - \frac{(n-2)!}{n^{n-2}} \sum_{k=1}^{n-1} \frac{n^{k-1}}{(k-1)!} \\
&=& \frac{(n-1)!}{n^{n-1}} \sum_{k=0}^{n-1} \frac{n^k}{k!} - \frac{(n-2)!}{n^{n-2}} \sum_{k=0}^{n-2} \frac{n^{k}}{k!} = \ldots
\end{eqnarray}
$$
Using, for $n\in \mathbb{N}$,
$$
   \frac{(n-1)!}{x^{n-1}} \sum_{k=0}^{n-1} \frac{x^k}{k!} = \mathrm{e}^x x^{1-n} \Gamma(n,x)
$$
and setting $x=n$ we continue
$$
 \ldots = \mathrm{e}^n n^{1-n} \Gamma(n,n) - \mathrm{e}^n n^{2-n} \Gamma(n-1,n) = \frac{n+1}{n-1} - \frac{1}{n-1} \frac{\mathrm{e}^n}{n^n} \Gamma(n+1,n)
$$
where the last equality used $n \Gamma(n,x) = \Gamma(n+1,x) - x^n \mathrm{e}^{-x}$ twice.
Now reusing the large $n$ asymptotic behavior of $\frac{\mathrm{e}^n}{n^n} \Gamma(n+1,n) \sim  \sqrt{\frac{\pi}{2} n }$ we arrive at the limit.
A: Let's consider a non-uniform partition where $x=\frac{i^2}{n}$ and $\mathrm{d}x=\frac{2i}{n}$; then we have $i=\sqrt{nx}$.
Note that
$$
\frac{(n-2)!}{(n-1-i)!n^{i-1}}
=\frac{n-2}{n}\frac{n-3}{n}\dots\frac{n-i}{n}
$$
Using, Bernoulli's Inequality, we get
$$
\left(1-\frac in\right)^{\frac2i+\frac3i+\dots+\frac ii}
\le\frac{n-2}{n}\frac{n-3}{n}\dots\frac{n-i}{n}
\le\left(1-\frac1n\right)^{2+3+\dots+i}\\
\left(1-\frac in\right)^{(i+2)(i-1)/(2i)}
\le\frac{(n-2)!}{(n-1-i)!n^{i-1}}
\le\left(1-\frac1n\right)^{(i+2)(i-1)/2}
$$
then using the squeeze theorem, we get that $\frac{(n-2)!}{(n-1-i)!n^{i-1}}\to e^{-x/2}$.
Summing to $i\le\sqrt{\lambda n}$ is equivalent to $x\le\lambda$, and this is equivalent to the Riemann sum for
$$
\begin{align}
\lim_{n\to\infty}n\sum_{i=1}^{\sqrt{\lambda n}}\frac{i(n-2)!}{(n-1-i)!n^{i+1}}
&=\lim_{n\to\infty}\sum_{i=1}^{\sqrt{\lambda n}}\frac{(n-2)!}{(n-1-i)!n^{i-1}}\frac in\\
&=\int_0^\lambda e^{-x/2}\,\frac{\mathrm{d}x}{2}\\
&=1-e^{-\lambda/2}
\end{align}
$$
Since $\lambda$ was arbitrary, we get that
$$
\lim_{n\to\infty}n\sum_{i=1}^{n-1}\frac{i(n-2)!}{(n-1-i)!n^{i+1}}=1
$$
