writes in his review of (a book about combinatorial proofs), these two simple techniques are enough to prove many theorems in combinatorics and number theory.

Example

An archetypal double counting proof is for the well known formula for the number of k-combinations (i.e., subsets of size k) of an n-element set:
:Here a direct bijective proof is not possible: because the right-hand side of the identity is a fraction, there is no set obviously counted

1.Previous
3.Next