Two basic identities for the binomial coefficients are contained in the equation . 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 board. If you can color each square in the board either black or white, there are ways to color the board.

There are also* n* grooves in this board: grooves between the squares plus a groove (numbered before the first square and a groove after the last square. Suppose we select an even number of those grooves: . We can then construct a coloring of the board by coloring black the squares between grooves , , and coloring the remaining squares white. This produces a coloring with *k* runs of black tiles. For example, if , selecting grooves 1, 3, 4, and 5 (so that ) yields the coloring WBBWBWWWW. There are ways to choose even numbers from *n.* Summing over all possible values of *k*, we have the number of ways to color the board as .

Instead of choosing an even number of grooves, we could also choose an odd number of grooves: . Now we color black the squares between grooves as before, but we also color black the squares between grooves and . Color the remaining squares white. This selection might not have runs of black tiles because might be . 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 . There are ways to choose odd numbers from *n*. Summing over all possible values of *k*, we also have the number of ways to color the board as .

Therefore, .

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**

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