Binomial Coefficients, Identities, and Combinatorial Proofs

What This Concept Is

Binomial coefficients are not only numbers in Pascal's triangle. $\binom{n}{k}$ is the count of $k$-element subsets of an $n$-element set, and that meaning lets you prove identities by interpretation rather than algebra alone.

A combinatorial proof (also called a double-counting proof) works like this:

1. define a set $S$ of objects precisely.
2. count $|S|$ in one way, producing expression $L$.
3. count $|S|$ in a different way, producing expression $R$.
4. conclude $L = R$ because both count the same set.

The power of the method is that the story is the proof. A successful combinatorial argument produces an identity and an intuition simultaneously; an algebraic manipulation only produces the identity.

Binomial coefficients also have analytic identities (from the binomial theorem $(1+x)^n = \sum_k \binom{n}{k} x^k$), recursive identities (Pascal's rule), and generating-function identities. The combinatorial view unifies many of these under one theme: the same set counted two ways.

Bijection vs double count. A closely related method is counting by bijection: establish an explicit one-to-one correspondence between two sets $A$ and $B$; conclude $|A| = |B|$. Double counting counts one set two ways; bijection matches two sets element-by-element. Both are combinatorial; most identities admit at least one of them, and many admit both.

Why It Matters Here

Combinatorial proof is where counting stops being a bag of formulas and becomes proof technique. Many graph-theory theorems (handshaking lemma, degree-sum identities, edge-counting inequalities) are combinatorial proofs in disguise. So are many probability arguments (linearity of expectation is essentially a double-count of incidence). And so are many algorithm analyses that count work across levels of a recursion.

A combinatorial proof also generalizes more robustly than algebra. If you prove $k\binom{n}{k} = n\binom{n-1}{k-1}$ algebraically, it applies to the specific binomial coefficients; if you prove it combinatorially as committee-and-chair, the story immediately generalizes to weighted counts, $q$-analogs, and multicombinatorial settings, giving you a family of identities at once.

Downstream, this style is the backbone of clean, intuition-rich proofs you will meet in Semester 2's algorithms course (cut-and-paste exchange arguments, incidence counts), Semester 4's database index cost analysis, and Semester 5's concurrency (counting happens-before pairs).

This concept is also the first time you will see two valid proofs of the same fact in this curriculum -- you should learn to judge proofs by clarity, not just correctness. The combinatorial version is usually shorter, more memorable, and easier to generalize; the algebraic version is usually mechanical and extends naturally to computer-algebra settings.

Concrete Examples

Example 1: Pascal's identity. Prove $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ for $1 \le k \le n-1$.

Interpret both sides as counting $k$-element subsets of ${1, 2, \ldots, n}$. Distinguish the element $n$:

• Case A (subsets not containing $n$): choose all $k$ elements from ${1, \ldots, n-1}$, giving $\binom{n-1}{k}$.
• Case B (subsets containing $n$): $n$ is forced in; choose the remaining $k-1$ from ${1, \ldots, n-1}$, giving $\binom{n-1}{k-1}$.

Cases A and B are disjoint (a subset either contains $n$ or does not) and exhaustive. Their sum equals $\binom{n}{k}$. $\blacksquare$

This is the recursive structure behind Pascal's triangle itself: row $n$ sits atop row $n-1$, with each entry equal to the sum of its two parents. Computing a single $\binom{n}{k}$ dynamically via this recurrence takes $O(nk)$ time -- an early example of dynamic programming, covered formally in Semester 3.

Example 2: committee-chair identity. Prove $k\binom{n}{k} = n\binom{n-1}{k-1}$.

Let $S$ be the set of (committee, chair) pairs where the committee is a $k$-subset of ${1, \ldots, n}$ and the chair is one of its members.

• Count 1 (committee first): choose the $k$-subset ($\binom{n}{k}$ ways), then choose a chair from within ($k$ ways). Total $k\binom{n}{k}$.
• Count 2 (chair first): choose the chair from ${1, \ldots, n}$ ($n$ ways), then choose the remaining $k-1$ members from the other $n-1$ people ($\binom{n-1}{k-1}$ ways). Total $n\binom{n-1}{k-1}$.

Both count $|S|$, so $k\binom{n}{k} = n\binom{n-1}{k-1}$. $\blacksquare$

Notice no algebra appeared. The identity dropped out of a carefully chosen set.

Example 3: Vandermonde's identity. Prove $\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$.

Let $S$ = set of $r$-element subsets of a set $X$ with $|X| = m+n$ that has been split into a "left" part $L$ of size $m$ and a "right" part $R$ of size $n$.

• Count 1 (whole): $|S| = \binom{m+n}{r}$ directly.
• Count 2 (by split): every $r$-subset of $X$ consists of some $k$ elements from $L$ and $r-k$ from $R$, where $0 \le k \le r$. The number of such subsets with exactly $k$ on the left is $\binom{m}{k}\binom{n}{r-k}$. Summing over $k$ gives $|S|$.

Therefore $\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$. $\blacksquare$

This identity powers Chu-Vandermonde convolutions in probability (sum of two independent binomials), hypergeometric distributions in sampling without replacement, and the structure of convolution in generating functions (cluster 3).

Common Confusion / Misconceptions

• "Story attached after algebra" pseudo-proofs. A combinatorial proof must start by defining the counted set precisely. If you write the algebra first and then sprinkle narrative on top, you have done algebra, not a combinatorial proof.
• Two different sets of equal size. A proof that counts two different sets happening to have the same cardinality in some examples is not valid. The correspondence or shared counting target must be explicit; one set, two counts -- or one bijection between two sets.
• Missing cases / overlapping cases. Cases must be disjoint and exhaustive. Forgetting an edge case (empty subset, boundary index) invalidates the sum.
• Confusing identity flavor. "The sum of row $n$ of Pascal's triangle is $2^n$" is a counting identity with two natural explanations (choose a subset vs. choose in/out for each element). Both are combinatorial, but different. Know which you are using.
• "Combinatorial is always easier than algebraic." Not always. Some identities (e.g., involving reciprocals, $\sum_k (-1)^k \binom{n}{k}/(k+1)$) are more natural analytically than combinatorially. Pick the tool that fits; combinatorial proofs are preferred when available, not forced.

How To Use It

When you see an identity, try the following workflow:

1. Identify a candidate object set that both sides might count. Binomial coefficients, sequences, functions, subsets, paths on a grid -- all are useful raw materials.
2. Ask whether one side counts by total selection and the other by cases.
3. Ask whether one side counts by a distinguished element (like the committee chair).
4. Check cases are disjoint and exhaustive.
5. Write the argument as: "Let $S$ = … Count 1: … Count 2: … Therefore …".
6. Verify on small $n$ (e.g., $n=3, k=1$) by hand to catch sign/boundary errors.
7. If no direct combinatorial route appears, try a generating-function or algebraic proof -- sometimes the identity is genuinely analytic.

Good combinatorial proofs often come from asking, "What hidden decision separates the objects into natural classes?"

Distinguished-element heuristic. A surprisingly high fraction of identities are unlocked by "mark one element and count by whether it is inside / outside a subset" or "mark one position and count by what lies there." Pascal's identity, committee-chair, and the hockey-stick identity all follow this pattern. When an identity has a factor of $n$ or $k$ that does not obviously correspond to anything, suspect a distinguished-element trick.

Writing a clean combinatorial proof. Three sentences, always in this order: (1) "Let $S$ be the set of ⟨object⟩." (2) "Counting $S$ by ⟨method 1⟩ gives $L$." (3) "Counting $S$ by ⟨method 2⟩ gives $R$." Anything more is usually superfluous; anything less is usually incomplete.

Transfer to the workshop model

Use this concept to justify or challenge one result in the workshop project. Specify the counted objects or graph semantics before interpreting any numerical output.

Check Yourself

1. Why is "count the same set in two ways" strictly stronger than "the formulas agree on small inputs"?
2. What role does a distinguished element play in double counting? Give two examples from this page.
3. Why must the case split be exhaustive? What fails if it is not?
4. Prove $\sum_{k=0}^n \binom{n}{k} = 2^n$ by a combinatorial argument.
5. Explain why Pascal's identity corresponds to the recursive construction of $k$-subsets by the element $n$'s in/out status.
6. A bijection between $A$ and $B$ is a stronger statement than $|A| = |B|$ alone. What extra information does the bijection provide?
7. When would you prefer a bijection proof over a double-count proof? Give a setting where bijection is cleaner (e.g., showing two lattice-path families have the same size).

Mini Drill or Application

Give a combinatorial proof of each. Write the set being counted before you write any equations.

1. $\sum_{k=0}^n \binom{n}{k} = 2^n$.
2. $k\binom{n}{k} = n\binom{n-1}{k-1}$ (redo from scratch without peeking).
3. $\sum_{k=0}^n k\binom{n}{k} = n \cdot 2^{n-1}$.
4. The Vandermonde identity $\binom{m+n}{r} = \sum_{k=0}^r \binom{m}{k}\binom{n}{r-k}$. (Hint: $r$-subsets of a set split into a part of size $m$ and a part of size $n$.)
5. $\binom{n}{k} = \binom{n}{n-k}$. (Hint: complement bijection.)
6. The hockey-stick identity $\sum_{i=k}^{n} \binom{i}{k} = \binom{n+1}{k+1}$. (Hint: count $(k+1)$-subsets of ${1, \ldots, n+1}$ by the largest element.)
7. $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$. (Hint: Vandermonde with $m = n, r = n$ plus the symmetry $\binom{n}{n-k} = \binom{n}{k}$.)
8. $\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \cdots + (-1)^n \binom{n}{n} = 0$ for $n \ge 1$. (Hint: pair each subset with its symmetric-difference companion obtained by toggling a fixed element; this gives a sign-reversing involution.)

Read This Only If Stuck

Use the bounded reading guide to locate the topic in MCS or Rosen. These links open indexes. Check the actual heading in your edition, read one targeted explanation, then reconstruct the argument with the book closed.

Double counting requires the same objects on both sides

For 1≤k≤n, count pairs (S,s) where S is a k-subset of n people and s∈S is distinguished. Choosing S first gives k·C(n,k); choosing s first gives n·C(n−1,k−1). The two constructions count the identical object set exactly once. Merely producing equal numerical answers is not this proof.

For sum C(n,k)=2^n, the disjoint cases are subset sizes k=0..n; the alternative encoding is a membership bit for each of the n elements. The empty subset contributes the k=0 term, including n=0. Transfer: give a two-case proof of Pascal's identity by whether a designated element belongs to the subset, carefully treating boundary values.

After your attempt use practice feedback and model contracts to check the argument.