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

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?

• Is the binomial coefficient correct in the form $\binom{i}{n}$ ? Commented Jul 31, 2015 at 5:11
• If numeric tests work, it should be for $\sum_{i = 0}^{n}\ln\binom{n}{i}\Big/n^2$ Commented Jul 31, 2015 at 5:14
• maybe you can use o'stolz theory Commented Jul 31, 2015 at 5:15

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.

• Can you please explain why the remainder is $O(n\log n)$ when you applied the Euler-Maclaurin formula? Commented Jul 31, 2015 at 7:05
• @GeorgSaliba, that comes from using the "first" Euler-Maclaurin sum formula, $$\sum_{i=1}^{n} f(i) = \int_1^n f(x)\,dx + \frac{f(n)+f(1)}{2} + \int_1^n P_1(x)f'(x)\,dx,$$ where $P_1(x)$ is the first periodic Bernoulli function and $$\left|\int_1^n P_1(x)f'(x)\,dx\right| \leq \frac{1}{2}\int_0^1 |f'(x)|\,dx.$$ Commented Jul 31, 2015 at 7:36
• @AntonioVargas I saw you posted a solution ... well done by the way ... but did not read carefully to see that you had used the EM Formula. I pursued that approach independently and carried out an expansion to $n^{-4}$ for the object of interest. I tested it numerically and it is extremely robust. If you have a chance, I'd love to hear your thoughts. Commented Aug 1, 2015 at 6:25

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}}$$