10
$\begingroup$

This recent question contains two proofs that $$\sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{(k+1)^2} = \frac{H_{n+1}}{n+1}.$$ One, by Antonio Vargas, uses a double integral. The other, by me, uses the absorption identity twice. I'd like to see a combinatorial proof, but I haven't managed to come up with one yet.

Some thoughts so far:

  1. Since the right-hand side is clearly not an integer for $n \geq 1$, we may need to interpret the identity as a probability. I would accept a combinatorial-based probability argument.
  2. Alternatively, we could turn both sides into integers by multiplying by $(n+1)!^2$. The new identity would be $$ \sum_{k=0}^n \binom{n}{k} \frac{(-1)^k (n+1)!^2}{(k+1)^2} = (n+1)! \, n! \, H_{n+1}.$$ I would accept a combinatorial proof of this version of the identity.
  3. We need a combinatorial interpretation of the harmonic numbers. There are two in this paper by Benjamin, Preston, and Quinn. The first is that $n! \, H_n$ is the number of permutations on $n+1$ elements that contain exactly two cycles. That implies that $\dfrac{H_n}{n+1}$ (very close to the right-hand side of the identity we want to prove) is the probability that a random permutation on $n+1$ elements contains exactly two cycles. The second interpretation in the paper is that a random permutation on $n$ elements has, on average, $H_n$ cycles.
  4. We likely need inclusion/exclusion to interpret the left-hand side.
$\endgroup$
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Note: You can remove all infinitary thinking from this proof. Just replace the sentence "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." by "Select two permutations $\left(x_1, x_2, \ldots, x_{n+1}\right)$ and $\left(y_1, y_2, \ldots, y_{n+1}\right)$ of the $\left(n+1\right)$-tuple $\left(1, 2, \ldots, n+1\right)$ uniformly and independently.". The resulting argument is a combinatorial proof of the original identity multiplied by $\left(n+1\right)!^2$. In theory, one could perhaps do better, but ... $\endgroup$ – darij grinberg Jan 15 at 20:16
  • $\begingroup$ ... not by much: In order to make all terms of the identity integers, one has to multiply by $\left(n+1\right) \cdot \operatorname{lcm}\left(1,2,\ldots,n+1\right)$, which for combinatorial purposes most likely means $\left(n+1\right) \cdot \left(n+1\right)!$. $\endgroup$ – darij grinberg Jan 15 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.