In a post from a couple of years ago I gave a probabilistic proof of the binomial coefficient identity
In this post I modify and generalize this proof to establish the identity
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 numbered red balls. Suppose we choose the balls one-by-one from the jar. Let 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 , 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 ways to arrange all balls. There are ways to order the blue balls, one way to order the black ball, and ways to order the red balls. This gives 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
The event is the event that the black ball is chosen before blue ball i. Thus, the intersection of any k of these ‘s with B is the event that the black ball is chosen first out of specific balls: the black one, the red ones, and k of the blue ones. This has probability . There are ways to select k of the ‘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
This argument is taken from my paper , 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.
- Michael Z. Spivey, “Probabilistic proofs of a binomial identity, its inverse, and generalizations.” American Mathematical Monthly, 123 (2): 175-180, 2016.