Calculate $\sum_{i = 0}^{n}\ln\binom{n}{i}\Big/n^2$

Question

Calculate $$\sum_{i = 0}^{n}\ln\binom{n}{i}\Big/n^2$$

I can only bound it as follows:

$$\binom{n}{i}<\left(\dfrac{n\cdot e}{k}\right)^k$$ $$\sum_{i = 0}^{n}\ln\binom{n}{i}\Big/n^2<\dfrac{1}{n}\dfrac{k}{n}\left(\ln(\dfrac{n}{k}\cdot e)\right)\rightarrow\int_0^1t\ln\dfrac{e}{t}dt=\dfrac{3}{4}$$

But numeric tests tell me the result seems to be $\dfrac{1}{2}$.

How can I achieve this?

Answer 1

Let $S(n)$ be the sum defined by

$$S(n)\equiv\frac{1}{n^2}\sum_{k=0}^{n}\log \binom{n}{k} \tag1$$

Expanding terms in $(1)$ yields

$$\begin{align} S(n)&=\frac{1}{n^2}\left((n+1)\log n!-2\sum_{k=0}^{n}\log k!\right)\\\\ &=\frac{1}{n^2}\left((n-1)\log n!-2\sum_{k=2}^{n-1}\log k!\right)\tag2 \end{align}$$

Substituting $\log k!=\sum_{\ell=2}^{k}\log \ell$ and simplifying terms reveals

$$S(n)=\frac{1}{n^2}\left(-(n+1)\log n!+2\sum_{k=1}^{n}k\log k\right)\tag3$$

Then, using the Euler-MacLaurin Formula, we can write the sum in $(3)$ as

$$\sum_{k=1}^{n}k\log k=\frac12 n^2\log n-\frac14 n^2+\frac12 n\log n\,+\frac{1}{12}\log n+\left(\frac14-\frac{1}{720}+\frac{1}{5040}\right)+\frac{1}{720}\frac{1}{n^2}-\frac{1}{5040}\frac{1}{n^4}+R$$

where a crude bound for the remainder $R$ can be shown to be given here by $|R|\le \frac{1}{630}$.

Similarly, the Euler-McLaurin Formula for $\log n!$ can be written

$$\log n!=n\log n-n+\frac12 \log n+\left(1- \frac{1}{12}+\frac{1}{720}\right)+\frac{1}{12}\frac{1}{n}-\frac{1}{720}\frac{1}{n^3}+R'$$

where a crude bound for the remainder $R'$ can be shown to be given here by $|R|\le\frac{1}{360}$.

Putting it all together reveals the expansion for $S$ as

$$\bbox[5px,border:2px solid #C0A000]{S\sim \frac12 -\frac12 \frac{\log n}{n}-\frac13 \frac{\log n}{n^2}+\left(\frac{1}{12}-\frac{1}{720}\right)\frac{1}{n}-\left(\frac{1}{2}+\frac{1}{240}\right) \frac{1}{n^2}-\frac{1}{12}\frac{1}{n^3}+\frac{1}{240}\frac{1}{n^4}}$$

Answer 2

One approach for calculating the limit as $n \to \infty$ is to use the Euler-Maclaurin sum formula twice.

We'll begin by rewriting

$$ \begin{align} \frac{1}{n^2} \sum_{i=0}^{n} \log \binom{n}{i} &= \frac{1}{n^2}\left[(n+1)\log n!-2\sum_{i=0}^{n} \log i!\right] \\ &= \frac{(n+1)\log n!}{n^2} - \frac{2}{n^2}\sum_{i=0}^{n} \log i!. \tag{1} \end{align} $$

Stirling's formula (via the Euler-Maclaurin formula) tells us that

$$ \log n! = n\log n - n + O(\log n) $$

as $n \to \infty$, so

$$ \frac{(n+1)\log n!}{n^2} = \log n - 1 + O\!\left(\frac{\log n}{n}\right). \tag{2} $$

For the remaining sum we'll again appeal to Stirling's formula to write it as

$$ \begin{align} \sum_{i=0}^{n} \log i! &= \sum_{i=1}^{n} i\log i - \sum_{i=1}^{n} i + O\!\left(\sum_{i=1}^{n} \log i \right) \\ &= \sum_{i=1}^{n} i\log i - \frac{1}{2}n^2 + O(n\log n). \end{align} $$

By Euler-Maclaurin

$$ \begin{align} \sum_{i=1}^{n} i\log i &= \int_1^n x\log x \,dx + O(n\log n) \\ &= \frac{1}{2}n^2 \log n - \frac{1}{4}n^2 + O(n\log n), \end{align} $$

and inserting this into the previous formula yields

$$ \sum_{i=0}^{n} \log i! = \frac{1}{2}n^2 \log n - \frac{3}{4}n^2 + O(n\log n). \tag{3} $$

Combining $(2)$ and $(3)$ in $(1)$ yields

$$ \begin{align} \frac{1}{n^2} \sum_{i=0}^{n} \log \binom{n}{i} &= \left[\log n - 1 + O\!\left(\frac{\log n}{n}\right)\right] + \left[- \log n + \frac{3}{2} + O\!\left(\frac{\log n}{n}\right)\right] \\ &= \frac{1}{2} + O\!\left(\frac{\log n}{n}\right), \end{align} $$

as desired.