# Is there any easier way to get the asymptotic value of this sum?

@Mike Spivey has proved in another question, that

$$S(n) = \sum_{k \geq 1} \frac{n!}{k (n-k)! n^k} = \sum_{k \geq 1} \frac{n^{\underline{k}}}{k n^k} \sim \frac{1}{2} \log(n).$$

But that proof is out of my ability to understand. So, is there more elementary way to prove it?

-
I have made edits that I think reflect Mike's original answer in the other question. Maybe I am alone in this, but when I see $1/2\log n$, I don't instinctively think/read one-half times log of n... – cardinal Oct 13 '11 at 1:04
@cardinal: No you aren't; either \frac{}{} or parentheses should really have been used to begin with to banish ambiguity. – J. M. Oct 13 '11 at 1:24
Hi ablmf, what is the definition of $n^{\underline{k}}$ ? – Leandro Oct 13 '11 at 1:34
@Leandro: See here. – cardinal Oct 13 '11 at 1:39
@cardinal thanks. – Leandro Oct 13 '11 at 2:50

The sum is $$\sum_{k=1}^n \frac{1}{k} (1-1/n)(1-2/n)\cdots (1-k/n)$$ As discussed in the earlier answer, $$(1-1/n) (1-2/n) \cdots (1-k/n) \approx e^{-k^2/(2n)}.$$
So the sum is roughly $$\sum_{k \geq 1} \frac{1}{k} e^{-k^2/(2n)} = \sum_{k \geq 1} \frac{1}{\sqrt{n}} \frac{\sqrt{n}}{k} e^{-(k/\sqrt{n})^2 /2}.$$
This is a Riemann sum approximation (with interval size $1/\sqrt{n}$) to the integral $$\int_{1/\sqrt{n}}^{\infty} \frac{dx}{x} e^{-x^2/2}$$ Let $[x<1]$ be $1$ for $x<1$ and $0$ for $x \geq 1$. Then the integral is $$\int_{1/\sqrt{n}}^{1} \frac{dx}{x} + \int_{1/\sqrt{n}}^{\infty} \frac{e^{-x^2/2} - [x<1]}{x} dx.$$ The first integral is $(1/2) \log n$. The second approaches $\int_{0}^{\infty} \frac{e^{-x^2/2} - [x<1]}{x} dx$, which is convergent.
So our final integral is $(1/2) \log n + O(1)$. I don't want to make too strong a claim about how much accuracy is lost in all the approximations, but one should be able to work it out.