International Mathematics Competition for University Students 2020

Select Year:

IMC 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

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).$

 IMC1994 IMC1995 IMC1996 IMC1997 IMC1998 IMC1999 IMC2000 IMC2001 IMC2002 IMC2003 IMC2004 IMC2005 IMC2006 IMC2007 IMC2008 IMC2009 IMC2010 IMC2011 IMC2012 IMC2013 IMC2014 IMC2015 IMC2016 IMC2017 IMC2018 IMC2019 IMC 2020