# Proved that question: S(n) = \sum_{k \geq 1} \frac{n!}{k (n-k)! n^k}

Proved that question:
$S\left(n\right)=\sum _{k\ge 1}\frac{n!}{k\left(n-k\right)!{n}^{k}}=\sum _{k\ge 1}\frac{{n}^{\underset{―}{k}}}{k{n}^{k}}\approx \frac{1}{2}\mathrm{log}\left(n\right)$
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Cloplerotly1gu
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}\left(1-\frac{1}{n}\right)\left(1-\frac{2}{n}\right)\cdots \left(1-\frac{k}{n}\right)$
As discussed in the earlier answer,
$\left(1-\frac{1}{n}\right)\left(1-\frac{2}{n}\right)\cdots \left(1-\frac{k}{n}\right)\approx {e}^{-\frac{{k}^{2}}{2n}}$
So the sum is roughly
$\sum _{k\ge 1}\frac{1}{k}{e}^{-\frac{{k}^{2}}{2n}}=\sum _{k\ge 1}\frac{1}{\sqrt{n}}\frac{\sqrt{n}}{k}{e}^{-\frac{{\left(\frac{k}{\sqrt{n}}\right)}^{2}}{2}}$
This is a Riemann sum approximation (with interval size $\frac{1}{\sqrt{n}}$) to the integral
Let $\left[x<1\right]$ be 1 for $x<1$ and 0 $x\ge 1$. Then the integral is
${\int }_{\frac{1}{\sqrt{n}}}^{1}\frac{dx}{x}+{\int }_{\frac{1}{\sqrt{n}}}^{\mathrm{\infty }}\frac{{e}^{-\frac{{x}^{2}}{2}}-\left[x<1\right]}{x}dx$
The first integral is $\left(\frac{1}{2}\right)\mathrm{log}n$. The second approaches ${\int }_{0}^{\mathrm{\infty }}\frac{{e}^{-\frac{{x}^{2}}{2}}-\left[x<1\right]}{x}dx$, which is convergent.
So our final integral is $\left(\frac{1}{2}\right)\mathrm{log}n+O\left(1\right)$