## 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  (p. 65 and p. 81, respectively) discusses both of these proofs.

References

1.  Arthur Benjamin and Jennifer Quinn, Proofs That Really Count, MAA, 2003.