Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 4 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.