uniolympiads Ελληνικά

IMC 2020, Day 2, Problem 8

Compute

lim⁡n→∞1log⁡log⁡n∑k=1n(−1)k(nk)log⁡k.\lim_{n \to \infty} \frac{1}{\log\log n} \sum_{k=1}^{n} (-1)^k \binom{n}{k} \log k.

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

Fedor Petrov, St. Petersburg State University

Original from the official PDFCompute n X 1 k n (−1) lim log k. n→∞ log log n k k=1 (Here log denotes the natural logarithm.) Fedor Petrov, St. Petersburg State University

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Fedor Petrov, St. Petersburg State University

Solution 1. Answer: 1.

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

∑(−1)k(nk)f(k)=∫(1−g)n.\sum (-1)^k \binom{n}{k} f(k) = \int (1 - g)^n.
To relate this to logarithm, we may use the Frullani integrals
∫0∞e−x−e−kxxdx=lim⁡c→+0∫c∞e−xxdx−∫c∞e−kxxdx=lim⁡c→+0∫c∞e−xxdx−∫kc∞e−xxdx=lim⁡c→+0∫ckce−xxdx=log⁡k+lim⁡c→+0∫ckce−x−1xdx=log⁡k.\begin{aligned} \int_0^\infty \frac{e^{-x} - e^{-kx}}{x}dx = \lim_{c\to+0}\int_c^\infty \frac{e^{-x}}{x}dx - \int_c^\infty \frac{e^{-kx}}{x}dx = \lim_{c\to+0}\int_c^\infty \frac{e^{-x}}{x}dx - \int_{kc}^\infty \frac{e^{-x}}{x}dx = \\ \lim_{c\to+0}\int_c^{kc} \frac{e^{-x}}{x}dx = \log k + \lim_{c\to+0}\int_c^{kc} \frac{e^{-x} - 1}{x}dx = \log k. \end{aligned}
This gives the integral representation of our sum:
A:=∑k=1n(−1)k(nk)log⁡k=∫0∞−e−x+1−(1−e−x)nxdx.A := \sum_{k=1}^n (-1)^k \binom{n}{k} \log k = \int_0^\infty \frac{-e^{-x} + 1 - (1 - e^{-x})^n}{x}dx.
Now the problem is reduced to a rather standard integral asymptotics.

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

0⩽∫M∞−e−x+1−(1−e−x)nxdx⩽n∫M∞e−xxdx⩽nM−1∫M∞e−xdx=nM−1e−M.0 \leqslant \int_M^\infty \frac{-e^{-x} + 1 - (1 - e^{-x})^n}{x}dx \leqslant n\int_M^\infty \frac{e^{-x}}{x}dx \leqslant nM^{-1}\int_M^\infty e^{-x}dx = nM^{-1}e^{-M}.
So choosing MM such that MeM=nMe^M = n (such MM exists and goes to ∞\infty with nn) we get
A=O(1)+∫0M−e−x+1−(1−e−x)nxdx.A = O(1) + \int_0^M \frac{-e^{-x} + 1 - (1 - e^{-x})^n}{x}dx.
Note that for 0⩽x⩽M0 \leqslant x \leqslant M we have e−x⩾e−M=M/ne^{-x} \geqslant e^{-M} = M/n, and (1−e−x)n−1⩽e−e−x(n−1)⩽e−M(n−1)/n(1 - e^{-x})^{n-1} \leqslant e^{-e^{-x}(n-1)} \leqslant e^{-M(n-1)/n} tends to 0 uniformly in xx. Therefore
∫0M(1−e−x)(1−(1−e−x)n−1)xdx=(1+o(1))∫0M1−e−xxdx.\int_0^M \frac{(1 - e^{-x})(1 - (1 - e^{-x})^{n-1})}{x}dx = (1 + o(1))\int_0^M \frac{1 - e^{-x}}{x}dx.
Finally
∫0M1−e−xxdx=∫011−e−xxdx+∫1M−e−xxdx+∫1Mdxx=log⁡M+O(1)=log⁡(M+log⁡M)+O(1)=log⁡log⁡n+O(1),\begin{aligned} \int_0^M \frac{1 - e^{-x}}{x}dx = \int_0^1 \frac{1 - e^{-x}}{x}dx + \int_1^M \frac{-e^{-x}}{x}dx + \int_1^M \frac{dx}{x} = \\ \log M + O(1) = \log(M + \log M) + O(1) = \log\log n + O(1), \end{aligned}
and we get A=(1+o(1))log⁡log⁡nA = (1 + o(1))\log\log n.

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

Expand the rational function

f(x)=m!x(x+1)…(x+m)f(x) = \frac{m!}{x(x+1)\ldots(x+m)}
as the linear combination of simple fractions f(x)=∑j=0mcj/(x+j)f(x) = \sum_{j=0}^m c_j/(x+j). To find cjc_j we use
cj=((x+j)f(x)) ∣x=−j=(−1)j(mj).c_j = ((x+j)f(x))\,|_{x=-j} = (-1)^j\binom{m}{j}.
So we get
∑k=0m(−1)k(mk)1x+k=m!x(x+1)…(x+m).(1)\sum_{k=0}^m (-1)^k \binom{m}{k} \frac{1}{x+k} = \frac{m!}{x(x+1)\ldots(x+m)}. \tag{1}
Another known identity we use is
∑k=j+1n(−1)k(nj)=∑k=j+1n(−1)k((n−1k)+(n−1k−1))=(−1)j+1(n−1j).(2)\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}. \tag{2}
Finally we write log⁡k=∫1kdxx=∑j=1k−1Ij\log k = \int_1^k \frac{dx}{x} = \sum_{j=1}^{k-1} I_j, where Ij=∫01dxx+jI_j = \int_0^1 \frac{dx}{x+j}. Now we have
S:=∑k=1n(−1)k(nk)log⁡k=∑k=1n(−1)k(nk)∑j=1k−1Ij=∑j=1n−1Ij∑k=j+1n(−1)k(nk)=(2)∑j=1n−1Ij(−1)j+1(n−1j)=∫01∑j=1n−1(−1)j+1(n−1j)dxx+j=∫01(1x−∑j=0n−1(−1)j(n−1j)dxx+j)dx=(1)∫01(1x−(n−1)!x(x+1)…(x+(n−1)))dx=∫01dxx(1−1(1+x)(1+x/2)…(1+x/(n−1))).\begin{aligned} 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} = \\ \int_0^1 \sum_{j=1}^{n-1} (-1)^{j+1}\binom{n-1}{j}\frac{dx}{x+j} = \int_0^1 \left(\frac{1}{x} - \sum_{j=0}^{n-1} (-1)^j \binom{n-1}{j}\frac{dx}{x+j}\right)dx \underset{(1)}{=} \\ \int_0^1 \left(\frac{1}{x} - \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). \end{aligned}
So SS is again expressed as an integral, for which it is not hard to get an asymptotics.

Since et⩾1+te^t \geqslant 1 + t for all real tt (by convexity or any other reason), we have ey2−y⩾1+y2−y=1+y31+y⩾11+ye^{y^2-y} \geqslant 1 + y^2 - y = \frac{1+y^3}{1+y} \geqslant \frac{1}{1+y} and 11+y⩾1ey=e−y\frac{1}{1+y} \geqslant \frac{1}{e^y} = e^{-y} for y>0y > 0. Therefore

ey2−y⩾11+y⩾e−y, y>0.e^{y^2-y} \geqslant \frac{1}{1+y} \geqslant e^{-y},\ y > 0.
Using this double inequality we get
ex2(1+122+…+1(n−1)2)−x(1+12+…+1n−1)⩾1(1+x)(1+x/2)…(1+x/(n−1))⩾e−x(1+12+…+1n−1).e^{x^2\left(1+\frac{1}{2^2}+\ldots+\frac{1}{(n-1)^2}\right) - x\left(1+\frac{1}{2}+\ldots+\frac{1}{n-1}\right)} \geqslant \frac{1}{(1+x)(1+x/2)\ldots(1+x/(n-1))} \geqslant e^{-x\left(1+\frac{1}{2}+\ldots+\frac{1}{n-1}\right)}.
Since x2(1+1/22+…)⩽2x2⩽2xx^2(1 + 1/2^2 + \ldots) \leqslant 2x^2 \leqslant 2x, we conclude that
1(1+x)(1+x/2)…(1+x/(n−1))=e−Cnx,where −2+∑j=1n−11j⩽Cn⩽∑j=1n−11j,\frac{1}{(1+x)(1+x/2)\ldots(1+x/(n-1))} = e^{-C_nx}, \text{where } -2 + \sum_{j=1}^{n-1}\frac{1}{j} \leqslant C_n \leqslant \sum_{j=1}^{n-1}\frac{1}{j},
i.e., Cn=log⁡n+O(1)C_n = \log n + O(1). Thus
S=∫01dxx(1−e−Cnx)=∫0Cndtt(1−e−t)=∫1Cndtt+∫01(1−e−t)dtt+∫1Cne−tdtt=log⁡Cn+O(1)=log⁡log⁡n+O(1).\begin{aligned} 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} \\ = \log C_n + O(1) = \log\log n + O(1). \end{aligned}

Transcribed from the official solutions, pages 5–6. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?