# Collection of less well-known, non-trivial, elegant story proofs (ie, “double counting proofs”) of combinatorial identities

By story proof I mean proving a combinatorial identity by counting the number of elements of some carefully chosen set in two different ways to obtain the different expressions in the identity. The following is my favorite:

Prove (try the algebraic method!) $$\sum _ { k = 0 } ^ { n } {n \choose k} 2 ^ { k } { {n - k }\choose { \left[ \frac { n - k } { 2 } \right]} } = { {2 n + 1 } \choose { n }},$$

Proof: Assume there are $$2n+1$$ people, where one of them T is single (it's me), the rest of them are $$n$$ pairs of lovers $$(a_n,b_n)$$. Now we need to choose $$n$$ among the $$2n+1$$ people for a dance party. There are $$2$$ methods:

A. Choose $$n$$ people arbitrarily, which accounts for $${ {2 n + 1 } \choose { n }}$$ combinations in total.

B. Fix $$k$$, where $$0\leq k \leq n$$. Choose $$k$$ pairs of lovers, and demand only one of them can go to the party, which accounts for $${n \choose k} 2 ^ { k }$$ combinations. Choose $${ \left[ \frac { n - k } { 2 } \right] }$$ from the remaining $$n-k$$ pairs, and the two of them don't need to be separated.

If $$n-k$$ is odd, $$k + 2 \left[ \frac { n - k } { 2 } \right] = n - 1,$$ T can also join the party!

If $$n-k$$ is even, $$k + 2 \left[ \frac { n - k } { 2 } \right] = n,$$ T cannot join the party :(

When $$k$$ is fixed, the total number of combinations of the $$n$$ people is $${ {n - k }\choose { \left[ \frac { n - k } { 2 } \right]} }$$. Let $$k$$ vary from $$0$$ to $$n$$, then method B produces $$\sum _ { k = 0 } ^ { n } {n \choose k} 2 ^ { k } { {n - k }\choose { \left[ \frac { n - k } { 2 } \right]} }$$ combinations.

As the 2 methods should result in the same number of combinations, the identity is proved.

Source: My variant of Gu Jian's proof from Collection of CMO (Chinese Mathematics Olympiad) Problems (Sorry for can't provide a picture as it's written in Chinese).

I would like to collect everyone's favorite story proof. Apologize if this is a duplicate.

Any other less well-known ones?