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 fair coin.  Thus the left side of Identity 1 is the probability of flipping a fair 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 fair coin n times.  Thus the right side of Identity 1 is also the probability of flipping a fair 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.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s