4
$\begingroup$

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.

Blue's link: https://en.wikipedia.org/wiki/Double_counting_(proof_technique)

Any other less well-known ones?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.