Combinatorial proof that $\sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{(k+1)^2} = \frac{H_{n+1}}{n+1}$

Solution 1:

I found a probabilistic proof with a combinatorial flavor. I'll post it here so this question is officially answered, as well as for anyone who may be interested in seeing it.

Select points $(x_1, y_1), (x_2, y_2), \ldots, (x_{n+1}, y_{n+1})$ independently from the bivariate uniform distribution on the unit square.

Each side is the probability that, for all $i \in \{2, 3, \ldots, n+1 \}$, either $x_1 < x_i$ or $y_1 < y_i$.

Left side: Let $A_i$ denote the event that either $x_1 < x_i$ or $y_1 < y_i$. We want $\cap_{i=2}^{n+1} A_i$, which can be calculated via inclusion-exclusion. To use inclusion-exclusion, we need the probability that $x_1 > x_i$ and $y_1 > y_i$ for any collection of $k$ of the points in $\{(x_2, y_2), \ldots, (x_{n+1}, y_{n+1})\}$. This is the probability that $x_1$ is the largest of $k+1$ randomly-chosen points and $y_1$ is the largest of $k+1$ randomly-chosen points. Since the $x_i$'s and $y_i$'s are independent, this is $\dfrac{1}{(k+1)^2}$. Therefore, one way of calculating the probability we're after is $$1 - \sum_{k=1}^n \binom{n}{k} \frac{(-1)^{k-1}}{(k+1)^2} = \sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{(k+1)^2}.$$

Right side: Condition on the position of $x_1$ in the ordering of the $x_i$'s from smallest to largest. The probability that $x_1$ is the smallest is $\dfrac{1}{n+1}$, the probability that $x_1$ is the second-smallest is $\dfrac{1}{n+1}$, and so forth, regardless of the position that $x_1$ takes in the ordering of the $x_i$'s. Then, given that $x_1$ is the $k+1$ smallest of the $x_i$'s, we must have $y_1 < y_j$ for each $j$ such that $x_j < x_1$. Since there are $k$ of these $y_j$, the probability that $y_1$ is smaller than all $k$ of them is $\dfrac{1}{k+1}$. Summing up, we get that the probability we're after is also $$\frac{1}{n+1} \sum_{k=0}^n \frac{1}{k+1} = \frac{H_{n+1}}{n+1}.$$