Discrete Math · Undergraduate

Combinatorial Proofs and Binomial Coefficient Identities

Quick answer

A combinatorial proof shows that two expressions are equal by explaining how each one counts the same collection. The binomial coefficient C(n, k) counts the k-element subsets of an n-element set, which makes many identities transparent. Pascal's rule C(n, k) = C(n − 1, k − 1) + C(n − 1, k) splits subsets by whether they contain one chosen element. Counting all subsets gives the row sum 2ⁿ, and choosing a committee and its chair two ways gives k·C(n, k) = n·C(n − 1, k − 1).

What you'll learn

  • Interpret C(n, k) as a count of subsets
  • Prove an identity by counting one set in two ways
  • Prove Pascal's rule, the row sum and the committee–chair identity
  • Use Vandermonde's identity and the hockey stick identity

Counting one thing two ways

The binomial coefficient (nk)\binom{n}{k} counts the ways to choose kk elements from a set of nn. A combinatorial proof of an identity describes one collection of objects and counts it twice, once in the way the left side counts and once as the right side does. Since both count the same thing, they are equal.

nnRow of Pascal’s triangleSum
011
11 12
21 2 14
31 3 3 18
41 4 6 4 116
51 5 10 10 5 132

Why double counting proves Pascal’s rule

Take a set of nn people and single out one of them, Pat. Every group of kk either includes Pat or does not.

  • Groups with Pat: choose the other k−1k - 1 from the remaining n−1n - 1: (n−1k−1)\binom{n-1}{k-1}.
  • Groups without Pat: choose all kk from the remaining n−1n - 1: (n−1k)\binom{n-1}{k}.

Every group falls in exactly one case, so the two counts add up to all groups: (nk)=(n−1k−1)+(n−1k)\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}. That is the rule that builds each row of Pascal’s triangle from the one above. No factorials were needed.

Worked examples

Common mistakes

Practice problems

  1. Give a combinatorial reason that (nk)=(nn−k)\binom{n}{k} = \binom{n}{n-k}.

    Answer

    Choosing the kk elements to include is the same as choosing the n−kn - k to leave out.

    Full solution

    Each kk-subset matches exactly one (n−k)(n - k)-subset, its complement.

  2. Verify Pascal’s rule for (63)\binom{6}{3}.

    Answer

    20=10+1020 = 10 + 10

    Full solution

    (52)=10\binom{5}{2} = 10 and (53)=10\binom{5}{3} = 10.

  3. Prove ∑k(nk)2=(2nn)\sum_k \binom{n}{k}^2 = \binom{2n}{n} using Vandermonde’s identity, and check n=4n = 4.

    Answer

    Set m=nm = n and r=nr = n, and use (nn−k)=(nk)\binom{n}{n-k} = \binom{n}{k}; for n=4n = 4, 1+16+36+16+1=70=(84)1 + 16 + 36 + 16 + 1 = 70 = \binom{8}{4}.

    Full solution

    Choosing nn people from nn women and nn men, with kk women, gives (nk)(nn−k)=(nk)2\binom{n}{k}\binom{n}{n-k} = \binom{n}{k}^2 ways.

  4. Check the hockey stick identity (22)+(32)+(42)+(52)=(63)\binom{2}{2} + \binom{3}{2} + \binom{4}{2} + \binom{5}{2} = \binom{6}{3}.

    Answer

    1+3+6+10=201 + 3 + 6 + 10 = 20

    Full solution

    (63)=20\binom{6}{3} = 20.

  5. Prove the hockey stick identity ∑i=kn(ik)=(n+1k+1)\sum_{i=k}^{n} \binom{i}{k} = \binom{n+1}{k+1} combinatorially.

    Answer

    Sort the (k+1)(k + 1)-subsets of {1,…,n+1}\{1, \ldots, n + 1\} by their largest element.

    Full solution

    If the largest element is i+1i + 1, the other kk come from {1,…,i}\{1, \ldots, i\}: (ik)\binom{i}{k} ways. Adding over ii from kk to nn counts every subset once.

  6. How many subsets of a 1010-element set have an even number of elements?

    Answer

    512512

    Full solution

    Pair subsets by adding or removing one fixed element; each pair has one even and one odd subset, so half of the 2102^{10} are even.

  7. Use the committee–chair identity to find ∑kk(nk)\sum_k k\binom{n}{k}.

    Answer

    n 2n−1n\,2^{n-1}

    Full solution

    ∑kk(nk)=n∑k(n−1k−1)=n 2n−1\sum_k k\binom{n}{k} = n\sum_k \binom{n-1}{k-1} = n\,2^{n-1}: choose a chair, then any subset of the others.

  8. A student “proves” the row sum by checking n=1,2,3,4n = 1, 2, 3, 4. What is missing?

    Answer

    An argument for every nn, such as counting subsets two ways.

    Full solution

    Cases can suggest an identity but cannot prove it for all nn; the double count does.

Frequently asked questions

What is a combinatorial proof?

A proof that two expressions are equal because both count the same set of objects, each in its own way.

How is Pascal's rule proved combinatorially?

Fix one element x of an n-element set. A k-subset either contains x (choose the other k − 1 from n − 1) or does not (choose all k from n − 1). So C(n, k) = C(n − 1, k − 1) + C(n − 1, k).

Why do the numbers in row n of Pascal's triangle add up to 2ⁿ?

Both sides count all subsets of an n-element set: by size on the left, and by deciding in or out for each element on the right.

What is Vandermonde's identity?

C(m + n, r) = Σₖ C(m, k)C(n, r − k): choose r people from m women and n men, sorted by how many women are chosen.

What is the hockey stick identity?

C(k, k) + C(k + 1, k) + ⋯ + C(n, k) = C(n + 1, k + 1). In Pascal's triangle, a diagonal run adds up to the entry diagonally below its end.

What to learn next