2
$\begingroup$

I am looking for an estimation or an approximation of

$\sum _{k=1}^{n}{\log(k)\binom {n}{k}}$

Any hints will be appreciated. Thank you.

$\endgroup$
0

3 Answers 3

4
$\begingroup$

For $\log n \ge 2$ $$\sum_{k=1}^n {n \choose k} \log(k) \ge \sum_{k=n/\log n}^n {n \choose k} \log(n/\log n)$$ $$=\sum_{k=1}^n {n \choose k} \log(n/\log n)-\sum_{k=1}^{n/\log n} {n \choose k} \log(n/\log n)$$ $$ \ge \sum_{k=1}^n {n \choose k} \log(n/\log n)-\frac{n/\log n}{n}\sum_{k=1}^n {n \choose k} \log(n/\log n)$$ $$ = \log(n/\log n)2^n- \log(n/\log n) 2^n/\log n$$ $$ = \log(n) 2^n(1-\frac1{\log n})(1-\frac{\log \log n}{\log n})$$ Together with the obvious bound $$\sum_{k=1}^n {n \choose k }\log(k) \le \sum_{k=1}^n {n \choose k }\log(n)=\log(n) 2^n$$ we get $$\frac{\sum_{k=1}^n {n \choose k }\log(k)}{\log(n) 2^n} \in [(1-\frac1{\log n})(1-\frac{\log \log n}{\log n}),1]$$

$\endgroup$
3
  • $\begingroup$ Thank you for the answer. Let me check it numerically. $\endgroup$
    – david
    Oct 30, 2019 at 18:23
  • $\begingroup$ @david What do you mean to check numerically? Those inequalities are true, so no numerical check is required! $\endgroup$ Oct 31, 2019 at 8:50
  • $\begingroup$ @mathcounterexamples.net I think it's pretty obvious what it means. It means to see if the inequalities are true for certain values of the parameters. The statement in your comment just indicates you don't see any reason to "check numerically"; I am confused why you asked "what do you mean to check numerically". In any event, I think numerical checks are important, as humans make mistakes in proofs sometimes. I find your comment of very low quality in many respects. $\endgroup$ Nov 16, 2019 at 10:43
2
$\begingroup$

I'm continuing the computations by Jack D'Aurizio (following myself). \begin{align}\sum_{k=1}^{n}\binom{n}{k}\ln k&=\sum_{k=1}^{n}\binom{n}{k}\int_0^1\frac{x^{k-1}-1}{\ln x}\,dx\\\color{gray}{[\text{note the sign}]}\quad&=\int_0^1\frac{(1+x)^n-1-(2^n-1)x}{x\ln x}\,dx\\\color{gray}{\text{[integrate by parts]}}\quad&=\int_0^1\big(2^n-1-n(1+x)^{n-1})\ln\ln\frac{1}{x}\,dx\\\color{gray}{[\text{substitute }x=2e^{-t}-1]}\quad&=-(2^n-1)\gamma-2^n n\int_0^{\ln 2}e^{-nt}\ln\ln\frac{1}{2e^{-t}-1}\,dt\\&=\color{blue}{2^n(\ln n-\ln 2-I_n)}+\underbrace{\gamma+2^n n\int_{\ln 2}^{\infty}e^{-nt}\ln 2t\,dt}_{\text{small, can be neglected}},\end{align} $$I_n=n\int_0^{\ln 2}e^{-nt}\varphi(t)\,dt,\qquad\varphi(t)=\ln\left[\frac{1}{2t}\ln\frac{1}{2e^{-t}-1}\right].$$ $I_n$ fits Watson's lemma: $\varphi(t)=\frac{1}{2}t+\frac{3}{8}t^2+\frac{1}{3}t^3+\frac{65}{192}t^4+\frac{67}{180}t^5+\ldots$ gives $$I_n\asymp\frac{1}{2n}+\frac{3}{4n^2}+\frac{2}{n^3}+\frac{65}{8n^4}+\frac{134}{3n^5}+\ldots$$

$\endgroup$
1
$\begingroup$

Interesting question. Frullani's integral provides an integral representation for $\log(k)$, $$ \log(k) = \int_{0}^{+\infty}\frac{e^{-x}-e^{-kx}}{x}\,dx $$ which in combination with the binomial theorem leads to $$ \begin{eqnarray*}\sum_{k=1}^{n}\log(k)\binom{n}{k} &=& \int_{0}^{+\infty}\left[(2^n-1)e^{-x}-(1+e^{-x})^n+1\right]\frac{dx}{x}\\&=&\int_{0}^{1}\underbrace{\frac{1-(1+t)^n+t(2^n-1)}{t\log(t)}}_{f_n(t)}\,dt.\end{eqnarray*} $$ Most of the mass of the integral comes from the right endpoint of the integration range, and since $$ \lim_{t\to 1^-}f_n(t) = 1+\left(\frac{n}{2}-1\right)2^n,\qquad \lim_{t\to 1^-}f_n'(t) = -\frac{1}{2}+\left(\frac{n^2}{8}-\frac{3n}{8}+\frac{1}{2}\right)2^n $$ we may approximate $$ \int_{0}^{1}f_n(t)\,dt \approx \int_{0}^{1} f_n(1^-)e^{-\frac{f_n'(1^-)}{f_n(1^-)}x}\,dx\approx \frac{2^{n+1}(n-2)^2}{n^2-3n+4}\left(1-e^{-\frac{n^2-3n+4}{4n-8}}\right). $$

$\endgroup$
5
  • $\begingroup$ Thank you, interesting answers. Let me do some numeric calculation to verify your results. $\endgroup$
    – david
    Oct 30, 2019 at 18:22
  • $\begingroup$ I'm quite sure using Frunalli leads to a better asymptotic than my elementary computation but Jack lose a $\log n$ term (because trivially the sum is $\ge 2^{n-1} \log (n/2)$) $\endgroup$
    – reuns
    Oct 30, 2019 at 18:26
  • $\begingroup$ @reuns: you're right, this approach leads to a worse approximation than yours. It is much better to exploit the fact that $\log$ is approximately constant on short intervals. $\endgroup$ Oct 30, 2019 at 18:33
  • $\begingroup$ Metamorphy claims a perfect asymptotic math.stackexchange.com/questions/711953/… with the same starting point as yours $\endgroup$
    – reuns
    Oct 30, 2019 at 18:34
  • $\begingroup$ @reuns: Indeed I lose accuracy when I replace $f_n(1-t)$ with a function of the form $A e^{-B t}$, metamorphy uses a more general approximation of the $A e^{-B t}\varphi(t)$ kind. $\endgroup$ Oct 30, 2019 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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