2
$\begingroup$

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

  • 1
    @Leandro: [See here](http://en.wikipedia.org/wiki/Pochhammer_symbol#Alternate_notations).2011-10-13

1 Answers 1

4

Here is a rough argument. Filling in the details should be elementary, but challenging. I find myself reusing several ideas from this earlier question.

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.