This month’s post entails proving the following equivalence:
Despite the fact that these two sums are over the same range and are equal for all values of n they are not equal term-by-term.
If you think about the two sides probabilistically, it’s not too hard to prove that they are equal. For example, is the probability of obtaining the rth head on the kth flip when repeatedly flipping a fair coin. Thus the left side of Identity 1 is the probability of flipping a fair coin n times and obtaining at least r heads. Similarly, is the probability of obtaining exactly k heads when flipping a fair coin n times. Thus the right side of Identity 1 is also the probability of flipping a fair coin n times and obtaining at least r heads. Therefore, the two sides must be equal.
A while back I was also interested in trying to prove algebraically that the two sides are equal. This turned out to be harder than it looked, and I thought I would record my derivation here. It’s a bit heavy on the algebra, I’m afraid. The overall goal will be to isolate the coefficient of on both sides of Identity 1, as each of the sides can be thought of as a polynomial in p. If these are equal then the identities must be equal.
The left side first. Expand using the binomial theorem to get
Now, which terms in this double sum contain a term? Those in which . Thus the coefficient of in this double sum is
Now for the right side of Identity 1. Expand using the binomial theorem to get
As before, which terms in this contain a term? Those in which . Thus the coefficient of in this double sum is
where the last expression comes from the formula for the partial alternating row sum of the binomial coefficients.