International Mathematics Competition
for University Students
2020

IMC2020: Day 2, Problem 8

Problem 8. Compute

\(\displaystyle \lim_{n\to \infty} \frac1{\log \log n}\sum_{k=1}^n (-1)^k\binom{n}{k} \log k. \)

(Here \(\displaystyle \log\) denotes the natural logarithm.)

Fedor Petrov, St. Petersburg State University

Solution 1. Answer: 1.

The idea is that if \(\displaystyle f(k)=\int g^k\), then

\(\displaystyle \sum (-1)^k\binom{n}{k} f(k)=\int (1-g)^n. \)

To relate this to logarithm, we may use the Frullani integrals

\(\displaystyle \int_0^\infty \frac{e^{-x}-e^{-kx}}xdx= \lim_{c\to +0} \int_c^\infty \frac{e^{-x}}xdx- \int_c^\infty \frac{e^{-kx}}xdx= \lim_{c\to +0} \int_c^\infty \frac{e^{-x}}xdx- \int_{kc}^\infty \frac{e^{-x}}xdx =\)

\(\displaystyle \lim_{c\to +0} \int_c^{kc} \frac{e^{-x}}xdx= \log k+\lim_{c\to +0} \int_c^{kc} \frac{e^{-x}-1}xdx =\log k. \)

This gives the integral representation of our sum:

\(\displaystyle A:=\sum_{k=1}^n (-1)^k\binom{n}{k} \log k= \int_0^\infty \frac{-e^{-x}+1-(1-e^{-x})^n}xdx. \)

Now the problem is reduced to a rather standard integral asymptotics.

We have \(\displaystyle (1-e^{-x})^n\geqslant 1-ne^{-x}\) by Bernoulli inequality, thus \(\displaystyle 0\leqslant -e^{-x}+1-(1-e^{-x})^n\leqslant ne^{-x}\), and we get

\(\displaystyle 0\leqslant \int_M^\infty \frac{-e^{-x}+1-(1-e^{-x})^n}xdx \leqslant n\int_M^\infty \frac{e^{-x}}xdx\leqslant nM^{-1}\int_M^\infty e^{-x}dx=nM^{-1}e^{-M}. \)

So choosing \(\displaystyle M\) such that \(\displaystyle Me^M=n\) (such \(\displaystyle M\) exists and goes to \(\displaystyle \infty\) with \(\displaystyle n\)) we get

\(\displaystyle A=O(1)+\int_0^M \frac{-e^{-x}+1-(1-e^{-x})^n}xdx. \)

Note that for \(\displaystyle 0\leqslant x\leqslant M\) we have \(\displaystyle e^{-x}\geqslant e^{-M}=M/n\), and \(\displaystyle (1-e^{-x})^{n-1}\leqslant e^{-e^{-x}(n-1)}\leqslant e^{-M(n-1)/n}\) tends to 0 uniformly in \(\displaystyle x\). Therefore

\(\displaystyle \int_0^M \frac{(1-e^{-x})(1-(1-e^{-x})^{n-1})}xdx =(1+o(1))\int_0^M \frac{1-e^{-x}}xdx. \)

Finally

\(\displaystyle \int_0^M \frac{1-e^{-x}}xdx= \int_0^1 \frac{1-e^{-x}}xdx+ \int_1^M \frac{-e^{-x}}xdx+ \int_1^M\frac{dx}x=\)

\(\displaystyle \log M+O(1)=\log(M+\log M)+O(1) =\log \log n+O(1), \)

and we get \(\displaystyle A=(1+o(1))\log\log n\).

Solution 2. We start with a known identity (a finite difference of \(\displaystyle 1/x\)).

Expand the rational function

\(\displaystyle f(x)=\frac{m!}{x(x+1)\ldots (x+m)}\)

as the linear combination of simple fractions \(\displaystyle f(x)=\sum_{j=0}^m c_j/(x+j)\). To find \(\displaystyle c_j\) we use

\(\displaystyle c_j=\left((x+j)f(x)\right)|_{x=-j}=(-1)^j \binom{m}j. \)

So we get

\(\displaystyle \sum_{k=0}^m(-1)^k\binom{m}k \frac1{x+k}=\frac{m!}{x(x+1)\ldots (x+m)}. \)

\(\displaystyle (1) \)

Another known identity we use is

\(\displaystyle \sum_{k=j+1}^n (-1)^k\binom{n}j= \sum_{k=j+1}^n (-1)^k\left(\binom{n-1}k+\binom{n-1}{k-1}\right)= (-1)^{j+1}\binom{n-1}j. \)

\(\displaystyle (2) \)

Finally we write \(\displaystyle \log k=\int_1^k \frac{dx}x= \sum_{j=1}^{k-1} I_j\), where \(\displaystyle I_j=\int_{0}^1\frac{dx}{x+j}\).

Now we have

\(\displaystyle S:=\sum_{k=1}^n (-1)^k\binom{n}{k} \log k = \sum_{k=1}^n (-1)^k\binom{n}{k}\sum_{j=1}^{k-1} I_j=\sum_{j=1}^{n-1} I_j\sum_{k=j+1}^n (-1)^k\binom{n}{k}\underset{(2)}{=} \sum_{j=1}^{n-1} I_j(-1)^{j+1}\binom{n-1}j=\)

\(\displaystyle \int_0^1 \sum_{j=1}^{n-1} (-1)^{j+1}\binom{n-1}j\frac{dx}{x+j}= \int_0^1 \left(\frac1x-\sum_{j=0}^{n-1} (-1)^{j}\binom{n-1}j\frac{dx}{x+j}\right)dx \underset{(1)}{=}\)

\(\displaystyle \int_0^1 \left(\frac1x-\frac{(n-1)!}{x(x+1)\ldots (x+(n-1))}\right) dx=\int_0^1 \frac{dx}x \left(1-\frac{1}{(1+x)(1+x/2)\ldots (1+x/(n-1))}\right). \)

So \(\displaystyle S\) is again expressed as an integral, for which it is not hard to get an asymptotics.

Since \(\displaystyle e^t\geqslant 1+t\) for all real \(\displaystyle t\) (by convexity or any other reason), we have \(\displaystyle e^{y^2-y}\geqslant 1+y^2-y =\frac{1+y^3}{1+y}\geqslant \frac1{1+y}\) and \(\displaystyle \frac1{1+y}\geqslant \frac1{e^y}=e^{-y}\) for \(\displaystyle y>0\). Therefore

\(\displaystyle e^{y^2-y}\geqslant \frac{1}{1+y}\geqslant e^{-y},\,y>0. \)

Using this double inequality we get

\(\displaystyle e^{x^2\left(1+\frac1{2^2}+\ldots+\frac1{(n-1)^2}\right) -x\left(1+\frac12+\ldots+\frac1{n-1}\right)} \geqslant \frac{1}{(1+x)(1+x/2)\ldots (1+x/(n-1))}\geqslant e^{-x\left(1+\frac12+\ldots+\frac1{n-1}\right)}. \)

Since \(\displaystyle x^2(1+1/2^2+\ldots)\leqslant 2x^2\leqslant 2x\), we conclude that

\(\displaystyle \frac{1}{(1+x)(1+x/2)\ldots (1+x/(n-1))}= e^{-C_n x}, \text{where}\, -2+\sum_{j=1}^{n-1}\frac1j\leqslant C_n\leqslant \sum_{j=1}^{n-1}\frac1j, \)

i.e., \(\displaystyle C_n=\log n+O(1)\). Thus

\(\displaystyle S=\int_0^1 \frac{dx}x(1-e^{-C_nx})= \int_0^{C_n} \frac{dt}t(1-e^{-t})= \int_1^{C_n}\frac{dt}t+ \int_0^1 (1-e^{-t})\frac{dt}t+\int_1^{C_n} e^{-t}\frac{dt}t\)

\(\displaystyle =\log C_n+O(1)=\log \log n+O(1). \)