## A Probabilistic Proof of a Binomial Coefficient Identity, Generalized

In a post from a couple of years ago I gave a probabilistic proof of the binomial coefficient identity

$\displaystyle \sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{k+1} = \frac{1}{n+1}.$

In this post I modify and generalize this proof to establish the identity

$\displaystyle (1) \:\:\:\:\:\: \sum_{k=0}^n \frac{(-1)^k}{m+k} = \frac{(m-1)! \, n!}{(m+n)!}.$

As in the original proof, we use a balls-and-jars interpretation.  Suppose we have a jar that contains a black ball, n numbered blue balls, and $m-1$ numbered red balls.  Suppose we choose the balls one-by-one from the jar.  Let $A_i$ be the event that the black ball is chosen after blue ball i.  Let B be the event that the black ball is chosen before all the red balls.  We argue that Identity (1) gives in two different ways the probability of $B \cap \bigcap_{i=1}^n A_i$, the event that all the blue balls are chosen, then the black ball, and then all the red balls.

The right side of Identity (1) is easier to explain.  There are $(m+n)!$ ways to arrange all $m+n$ balls.  There are $(m-1)!$ ways to order the blue balls, one way to order the black ball, and $n!$ ways to order the red balls.  This gives $\displaystyle \frac{(m-1)! \, n!}{(m+n)!}$ as the probability that all the blue balls are selected, then the black ball, and then all of the red balls.

For the left side of Identity (1) we need the principle of inclusion/exclusion.  A slight generalization of one version of it says that

$\displaystyle P \left(B \cap \bigcap_{i=1}^n A_i \right) = P(B) - \sum_{i=1}^n P(B \cap \bar{A}_i) + \sum_{1 \leq i < j \leq n} P(B \cap \bar{A}_i \cap \bar{A}_j) \\ - \sum_{1 \leq i < j < k \leq n} P(B \cap \bar{A}_i \cap \bar{A}_j \cap \bar{A}_k) + \cdots + (-1)^n P(B \cap \bar{A}_1 \cap \cdots \cap \bar{A}_n).$

The event $\bar{A}_i$ is the event that the black ball is chosen before blue ball i.  Thus, the intersection of any k of these $\bar{A}_i$‘s with B is the event that the black ball is chosen first out of $m+k$ specific balls: the black one, the $m-1$ red ones, and k of the blue ones.  This has probability $1/(m+k)$.  There are $\binom{n}{k}$ ways to select k of the $\bar{A}_i$‘s.  By this generalized inclusion/exclusion principle, then, the probability that the black ball is chosen after the blue balls but before any of the red balls is also given by

$\displaystyle \sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{m+k}$.

This argument is taken from my paper [1], where I give a probabilistic proof of the binomial inverse of Identity (1), as well as proofs of generalizations of both (1) and its binomial inverse.

References

1.  Michael Z. Spivey, “Probabilistic proofs of a binomial identity, its inverse, and generalizations.” American Mathematical Monthly, 123 (2): 175-180, 2016.