Best solutions to - "Proved that question:S(n)=∑k≥1n!k(n−k)!nk=∑k≥1nk―knk≈12log⁡(n)"

calcolare45pj

Answered question

2022-03-30

Proved that question:

S (n) = \sum_{k \geq 1} \frac{n!}{k (n - k)! n^{k}} = \sum_{k \geq 1} \frac{n^{\underset{―}{k}}}{k n^{k}} \approx \frac{1}{2} \log (n)

Answer & Explanation

Karsyn Wu

Beginner2022-03-31Added 17 answers

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 - \frac{1}{n}) (1 - \frac{2}{n}) \dots (1 - \frac{k}{n})

As discussed in the earlier answer,

(1 - \frac{1}{n}) (1 - \frac{2}{n}) \dots (1 - \frac{k}{n}) \approx e^{- \frac{k^{2}}{2 n}}

So the sum is roughly

\sum_{k \geq 1} \frac{1}{k} e^{- \frac{k^{2}}{2 n}} = \sum_{k \geq 1} \frac{1}{\sqrt{n}} \frac{\sqrt{n}}{k} e^{- \frac{{(\frac{k}{\sqrt{n}})}^{2}}{2}}

This is a Riemann sum approximation (with interval size

\frac{1}{\sqrt{n}}

) to the integral
Let

[x < 1]

be 1 for

x < 1

and 0

x \geq 1

. Then the integral is

\int_{\frac{1}{\sqrt{n}}}^{1} \frac{d x}{x} + \int_{\frac{1}{\sqrt{n}}}^{\infty} \frac{e^{- \frac{x^{2}}{2}} - [x < 1]}{x} d x

The first integral is

(\frac{1}{2}) \log n

. The second approaches

\int_{0}^{\infty} \frac{e^{- \frac{x^{2}}{2}} - [x < 1]}{x} d x

, which is convergent.
So our final integral is

(\frac{1}{2}) \log n + O (1)

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Calculus 2

Didn't find what you were looking for?