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.
Advertisements
This entry was posted in binomial coefficients, probability. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s