Double Counting

Double counting (also called counting in two ways) is a proof technique where you count the elements of a set $S$ using two different methods, then equate the results. Concrete example — Handshaking Lemma: In any graph, the sum of all vertex degrees equals twice the number of edges. Why? Count the set of (vertex, edge) pairs where the vertex is an endpoint of the edge. Method 1: For each vertex $v$, it contributes $\deg(v)$ pairs, giving $\sum_v \deg(v)$. Method 2: Each edge contributes exactly 2 pairs (one per endpoint), giving $2|E|$. Therefore: $$\sum_{v} \deg(v) = 2|E|$$ Concrete example — Vandermonde's Identity: Count the ways to choose $r$ people from a group of $m$ men and $n$ women. Directly: $\binom{m+n}{r}$. By cases (choose $k$ men and $r-k$ women): $$\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$$ The power of double counting: It transforms a combinatorial identity from something you need to "verify algebraically" into something you can *see*. Instead of manipulating factorials, you define a set and count it two ways. When to use: Proving combinatorial identities, deriving bounds in extremal combinatorics, and any time you see a sum that equals a simpler expression. If two quantities "should" be equal, try to find a set they both count.