Two Methods for Proving an Alternating Binomial Identity

Recently I gave an optional homework problem in which I asked students to prove the following binomial identity:

\displaystyle \sum_{k=0}^n \binom{n}{k} \frac{2^k}{k+1} (-1)^k = \frac{1}{n+1} [ n \text{ is even}].

(Here, I’m using the Iverson bracket notation [P] in which [P] = 1 if P is true and [P] =  0 if P is false.)

I intended for students to use the following approach.

Method 1.

First, prove the identity

\displaystyle \sum_{k=0}^n \binom{n}{2k}\frac{1}{2k+1} = \frac{2^n}{n+1}.

This was an earlier problem in the exercises, so the students could have just cited it.  But let’s prove it with the absorption identity, \displaystyle \binom{n}{k} \frac{n+1}{k+1} = \binom{n+1}{k+1}.

Rewriting the absorption identity, we have \displaystyle \binom{n}{2k} \frac{n+1}{2k+1} = \binom{n+1}{2k+1}.  Then

\displaystyle \sum_{k=0}^n \binom{n}{2k}\frac{1}{2k+1} = \frac{1}{n+1} \sum_{k=0}^n \binom{n+1}{2k+1} = \frac{2^{n+1}}{2(n+1)} = \frac{2^n}{n+1}.

(Here, the second summation is just adding up the odd-index numbers in row n+1 of Pascal’s triangle.  This is known to be half the value of the sum of the numbers in row n+1; i.e., half of 2^{n+1}.)

Now that we’ve proved this identity, let’s rewrite it as

\displaystyle \sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{k+1} [k \text{ is even}] = \frac{2^n}{n+1}.

(Notice how the left side is the same as the left side in the identity we just proved because all the odd-index terms are zero.)  Now we can apply binomial inversion to get

\displaystyle \sum_{k=0}^n \binom{n}{k} \frac{2^k}{k+1} (-1)^k = \frac{1}{n+1} [n \text{ is even}].

This was a fairly hard problem to do this way in the sense that it’s likely not clear by looking at the first identity we proved that you can rewrite it in such a way that binomial inversion can be used.  However, my student Jiawen (Christine) Li found an easier way to prove the original identity by using the absorption property directly.  Christine’s proof comprises Method 2.

Method 2.

Applying the absorption identity, we have

\displaystyle \sum_{k=0}^n \binom{n}{k} \frac{2^k}{k+1} (-1)^k = \frac{1}{n+1} \sum_{k=0}^n \binom{n+1}{k+1} (-2)^k = \frac{1}{n+1} \sum_{k=1}^{n+1} \binom{n+1}{k} (-2)^{k-1} = \frac{-1}{2(n+1)} \sum_{k=1}^{n+1} \binom{n+1}{k} (-2)^k = \frac{-1}{2(n+1)} \left( \sum_{k=0}^n \binom{n+1}{k} (-2)^k - 1 \right) = \frac{-1}{2(n+1)} \left( (-1)^{n+1} - 1\right) = \frac{1}{2(n+1)} \left( (-1)^n + 1 \right) = \frac{2}{2(n+1)} [n \text{ is even}] = \frac{1}{n+1} [ n \text{ is even}].

For more examples with the absorption identity, see this post.

Advertisements
This entry was posted in binomial coefficients, combinatorics. 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