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

Bronson Olson 2022-05-02 Answered
Proved that question:
S(n)=k1n!k(nk)!nk=k1nkknk12log(n)
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Cloplerotly1gu
Answered 2022-05-03 Author has 11 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
k=1n1k(11n)(12n)(1kn)
As discussed in the earlier answer,
(11n)(12n)(1kn)ek22n
So the sum is roughly
k11kek22n=k11nnke(kn)22
This is a Riemann sum approximation (with interval size 1n) to the integral
Let [x<1] be 1 for x<1 and 0 x1. Then the integral is
1n1dxx+1nex22[x<1]xdx
The first integral is (12)logn. The second approaches 0ex22[x<1]xdx, which is convergent.
So our final integral is (12)logn+O(1)
Not exactly what you’re looking for?
Ask My Question

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more