Binomial identities, and proving them by counting twice

Every binomial identity worth knowing has a one-sentence combinatorial proof: find a set that both sides count, and describe the two ways of counting it. That technique is faster than algebra, harder to get wrong, and it is what an interviewer is hoping to hear.

Proposition 2.1

Count one thing two ways

To prove $A = B$ , find a collection of objects and show that $A$ counts it and so does $B$ . Nothing else is required — no induction, no manipulation of factorials. The whole skill is choosing the collection, and the right choice is usually suggested by whichever side has the more elaborate structure.

Holds when

The proof is complete once both counts are described. Resist the urge to verify it algebraically as well.
If you cannot find the set, the algebraic route still works; it is just longer and easier to slip on.

Identity	The set both sides count
$\binom{n}{k} = \binom{n}{n-k}$	Subsets of size $k$ — choose who is in, or who is out
$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$	Subsets of size $k$ , split on whether item $n$ is in
$k\binom{n}{k} = n\binom{n-1}{k-1}$	Committees of size $k$ with a chair
$\sum_k \binom{n}{k} = 2^n$	All subsets — by size, or by including each item or not
$\sum_k (-1)^k\binom{n}{k} = 0$	Even and odd subsets, which are equinumerous for $n \ge 1$
$\sum_{i}\binom{m}{i}\binom{n}{k-i} = \binom{m+n}{k}$	Size- $k$ subsets of two groups, split by how many come from the first
$\sum_{i=k}^{n}\binom{i}{k} = \binom{n+1}{k+1}$	Size- $(k{+}1)$ subsets of $\{0..n\}$ , split on the largest element

Table 2.2 · The identities, and what they count. The last two are Vandermonde and the hockey stick. Both are proved by conditioning on one feature of the object — where the elements came from, or what the maximum is.

Derivation 2.3

The committee and its chair

The cleanest example of the technique. Count committees of $k$ people drawn from $n$ , each with a designated chair.

$k\binom{n}{k}$
Choose the committee, then choose its chair from within it.
$n\binom{n-1}{k-1}$
Choose the chair from everyone, then fill the remaining $k-1$ seats.
$\text{Same objects, two descriptions}$

k\binom{n}{k} = n\binom{n-1}{k-1}

Pascal’s triangle is the recursion. Every entry is the sum of the two above it, which is just the statement that a subset either contains the last item or does not. Knowing the first several rows by sight is worth more than it sounds: $\binom{n}{2} = n(n-1)/2$ turns up constantly, the row sums are powers of two, and the alternating sums vanish. If you can picture the triangle you can reconstruct most of the table above.

Figure 2.4 · Pascal’s rule is a split on the last item. Choose two of four items. If item 4 is included, choose one of the other three: 3 ways. If it is excluded, choose two of the other three: 3 ways. These disjoint cases give C(4,2) = C(3,1) + C(3,2) = 6.

Binomial identities, and proving them by counting twice

After this lesson you should be able to

Count one thing two ways

The committee and its chair

The rest of this lesson is in Premium