IMC 2020 · Day 2 · P8

Answer: 1.

The idea is that if $f(k) = \int g^k$, then $$\sum (-1)^k \binom{n}{k} f(k) = \int (1 - g)^n.$$ To relate this to logarithm, we may use the Frullani integrals $$\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.$$ This gives the integral representation of our sum: $$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 \geqslant 1 - n e^{-x}$ by Bernoulli inequality, thus $0 \leqslant -e^{-x} + 1 - (1 - e^{-x})^n \leqslant n e^{-x}$, and we get $$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 n M^{-1} \int_M^\infty e^{-x}\,dx = n M^{-1} e^{-M}.$$ So choosing $M$ such that $M e^M = n$ (such $M$ exists and goes to $\infty$ with $n$) we get $$A = O(1) + \int_0^M \frac{-e^{-x} + 1 - (1 - e^{-x})^n}{x}\,dx.$$ Note that for $0 \leqslant x \leqslant M$ we have $e^{-x} \geqslant e^{-M} = M / n$, and $(1 - e^{-x})^{n-1} \leqslant e^{-e^{-x} (n-1)} \leqslant e^{-M (n-1)/n}$ tends to 0 uniformly in $x$. Therefore $$\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 $$\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),$$ and we get $A = (1 + o(1)) \log \log n$.

We start with a known identity (a finite difference of $1/x$).

Expand the rational function $$f(x) = \frac{m!}{x (x + 1) \dots (x + m)}$$ as the linear combination of simple fractions $f(x) = \sum_{j=0}^{m} c_j / (x + j)$. To find $c_j$ we use $$c_j = ((x + j) f(x)) \big|_{x = -j} = (-1)^j \binom{m}{j}.$$ So we get $$\tag{1} \sum_{k=0}^{m} (-1)^k \binom{m}{k} \frac{1}{x + k} = \frac{m!}{x (x + 1) \dots (x + m)}.$$ Another known identity we use is $$\tag{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}. Finally we write $\log k = \int_1^k \frac{dx}{x} = \sum_{j=1}^{k-1} I_j$, where $I_j = \int_0^1 \frac{dx}{x + j}$.

Now we have $$\begin{align*} 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} \overset{(2)}{=} \sum_{j=1}^{n-1} I_j (-1)^{j+1} \binom{n-1}{j} = \\ &= \int_0^1 \left( \sum_{j=1}^{n-1} (-1)^{j+1} \binom{n-1}{j} \frac{1}{x + j} \right) dx = \int_0^1 \left( \frac1x - \sum_{j=0}^{n-1} (-1)^j \binom{n-1}{j} \frac{1}{x + j} \right) dx \overset{(1)}{=} \\ &= \int_0^1 \left( \frac1x - \frac{(n-1)!}{x (x+1) \dots (x + (n-1))} \right) dx = \int_0^1 \frac{dx}{x} \left( 1 - \frac{1}{(1 + x)(1 + x/2) \dots (1 + x/(n-1))} \right). \end{align*}$$ So $S$ is again expressed as an integral, for which it is not hard to get an asymptotics.

Since $e^t \geqslant 1 + t$ for all real $t$ (by convexity or any other reason), we have $e^{y^2 - y} \geqslant 1 + y^2 - y = \frac{1 + y^3}{1 + y} \geqslant \frac{1}{1 + y}$ and $\frac{1}{1 + y} \geqslant \frac{1}{e^y} = e^{-y}$ for $y > 0$. Therefore $$e^{y^2 - y} \geqslant \frac{1}{1 + y} \geqslant e^{-y}, \quad y > 0.$$ Using this double inequality we get $$e^{x^2 \left( 1 + \frac{1}{2^2} + \dots + \frac{1}{(n-1)^2} \right) - x \left( 1 + \frac12 + \dots + \frac{1}{n-1} \right)} \geqslant \frac{1}{(1 + x)(1 + x/2) \dots (1 + x/(n-1))} \geqslant e^{-x \left( 1 + \frac12 + \dots + \frac{1}{n-1} \right)}.$$ Since $x^2 (1 + 1/2^2 + \dots) \leqslant 2 x^2 \leqslant 2x$, we conclude that $$\frac{1}{(1 + x)(1 + x/2) \dots (1 + x/(n-1))} = e^{-C_n x}, \quad \text{where } -2 + \sum_{j=1}^{n-1} \frac1j \leqslant C_n \leqslant \sum_{j=1}^{n-1} \frac1j,$$ i.e., $C_n = \log n + O(1)$. Thus $$S = \int_0^1 (1 - e^{-C_n x}) \frac{dx}{x} = \int_0^{C_n} (1 - e^{-t}) \frac{dt}{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).S=∫01​(1−e−Cn​x)xdx​=∫0Cn​​(1−e−t)tdt​=∫1Cn​​tdt​+∫01​(1−e−t)tdt​+∫1Cn​​e−ttdt​=logCn​+O(1)=loglogn+O(1).