## Equivalence of Two Binomial Sums

This month’s post entails proving the following equivalence:

Identity 1: $\displaystyle \sum_{k=r}^n \binom{k-1}{r-1} p^r (1-p)^{k-r} = \sum_{k=r}^n \binom{n}{k} p^k (1-p)^{n-k}.$

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, $\binom{k-1}{r-1} p^r (1-p)^{k-r}$ is the probability of obtaining the rth head on the kth flip when repeatedly flipping a coin that has a probability p of being heads.  Thus the left side of Identity 1 is the probability of flipping a coin times and obtaining at least r heads.  Similarly, $\binom{n}{k} p^k (1-p)^{n-k}$ is the probability of obtaining exactly k heads when flipping a coin n times (again, in which p is the probability of achieving heads on a single flip).  Thus the right side of Identity 1 is also the probability of flipping a coin 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 $p^m$ 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 $(1-p)^{k-r}$ using the binomial theorem to get

$\displaystyle \sum_{k=r}^n \binom{k-1}{r-1} p^r (1-p)^{k-r} = p^r \sum_{k=r}^n \binom{k-1}{r-1} \sum_{j=0}^{k-r} \binom{k-r}{j} (-p)^j$.

Now, which terms in this double sum contain a $p^m$ term?  Those in which $j = m-r$.  Thus the coefficient of $p^m$ in this double sum is

$\displaystyle \sum_{k=r}^n \binom{k-1}{r-1} \binom{k-r}{m-r} (-1)^{m-r} = \sum_{k=m}^n \binom{k-1}{r-1} \binom{k-r}{m-r} (-1)^{m-r}$

$\displaystyle = (-1)^{m-r} \sum_{k=m}^n \frac{r}{k} \binom{k}{r} \binom{k-r}{m-r}, \text{ by the absorption identity}$

$\displaystyle = (-1)^{m-r} r \sum_{k=m}^n \frac{1}{k} \binom{k}{m} \binom{m}{r}, \text{ by trinomial revision}$

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

$\displaystyle = (-1)^{m-r} r \binom{m}{r} \sum_{k=m}^n \binom{k-1}{m-1} \frac{1}{m}, \text{ by the absorption identity (again)}$

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

$\displaystyle = (-1)^{m-r} \binom{m-1}{r-1} \binom{n}{m}, \text{ by, once more, the absorption identity, plus the hockey stick identity}.$

Now for the right side of Identity 1.  Expand $(1-p)^{n-k}$ using the binomial theorem to get

$\displaystyle \sum_{k=r}^n \binom{n}{k} p^k (1-p)^{n-k} = \sum_{k=r}^n \binom{n}{k} p^k \sum_{j=0}^{n-k} \binom{n-k}{j} (-p)^j$.

As before, which terms in this contain a $p^m$ term?  Those in which $j = m-k$.  Thus the coefficient of $p^m$ in this double sum is

$\displaystyle \sum_{k=r}^n \binom{n}{k} \binom{n-k}{m-k} (-1)^{m-k} = \sum_{k=r}^m \binom{n}{k} \binom{n-k}{m-k} (-1)^{m-k}$

$\displaystyle = \sum_{k=r}^m \binom{n}{m} \binom{m}{k} (-1)^{m-k}, \text{ by trinomial revision}$

$\displaystyle = \binom{n}{m} \sum_{k=0}^{m-r} \binom{m}{m-k} (-1)^k, \text{ reindexing the sum}$

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

$\displaystyle = \binom{n}{m} (-1)^{m-r} \binom{m-1}{r-1},$

where the last expression comes from the formula for the partial alternating row sum of the binomial coefficients.