Tiling Proofs for the Sum of Even or Odd-Indexed Binomial Coefficients

Two basic identities for the binomial coefficients are contained in the equation \displaystyle \sum_{k \geq 0} \binom{n}{2k} = \sum_{k \geq 0} \binom{n}{2k+1} = 2^{n-1}.   There are multiple ways to prove these identities (even if you restrict yourself to combinatorial proofs).  In this post I’m going to discuss a tiling or coloring-based combinatorial proof that I find aesthetically satisfying.

Proof: Suppose you have a 1 \times (n-1) board.  If you can color each square in the board either black or white, there are 2^{n-1} ways to color the board.

There are also n grooves in this board: n-2 grooves between the squares plus a groove (numbered 0 before the first square and a groove after the last square.  Suppose we select an even number 2k of those grooves: a_1, a_2, \ldots, a_{2k}.  We can then construct a coloring of the board by coloring black the squares between grooves [a_{2i-1}, a_{2i}], 1 \leq i \leq k, and coloring the remaining squares white.  This produces a coloring with k runs of black tiles.  For example, if n = 10, selecting grooves 1, 3, 4, and 5 (so that k = 2) yields the coloring WBBWBWWWW.  There are \binom{n}{2k} ways to choose 2k even numbers from n.  Summing over all possible values of k, we have the number of ways to color the board as \displaystyle \sum_{k \geq 0} \binom{n}{2k}.

Instead of choosing an even number of grooves, we could also choose an odd number 2k+1 of grooves: a_0, a_1, \ldots, a_{2k}.  Now we color black the squares between grooves [a_{2i-1}, a_{2i}] as before, but we also color black the squares between grooves 0 and a_0.  Color the remaining squares white.  This selection might not have k+1 runs of black tiles because a_0 might be 0.  However, it will have exactly k transitions from a white run to a black run.  For example, selecting grooves 0, 1, 3, 4, and 5 produces the same coloring WBBWBWWWW as in the previous example.  It has two white-to-black transitions, and k = 2.  There are \binom{n}{2k+1} ways to choose 2k+1 odd numbers from n.  Summing over all possible values of k, we also have the number of ways to color the board as \displaystyle \sum_{k \geq 0} \binom{n}{2k+1}.

Therefore, \displaystyle \sum_{k \geq 0} \binom{n}{2k} = \sum_{k \geq 0} \binom{n}{2k+1} = 2^{n-1}.


There are simpler combinatorial proofs of these identities.  For example, one can count the number of ways to form, out of n people, a committee with an even only or odd only number of members.  One can also construct a one-to-one mapping between even-sized committees and odd-sized committees, showing that there must be an equal number of each.  Proofs That Really Count [1] (p. 65 and p. 81, respectively) discusses both of these proofs.

References

  1.  Arthur Benjamin and Jennifer Quinn, Proofs That Really Count, MAA, 2003.
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