## 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.