Proving C(n,k) = C(n,n-k)

Intro to Proofs · Axiom Academy

A combinatorial proof: choosing k items to include is the same as choosing n-k items to exclude Prove the identity combinatorially — not by algebra, but by showing both sides count the very same collection of objects. We'll build a bijection between the k -subsets and the (n-k) -subsets of an n -element set, using the concrete case n = 5 , k = 2 to see it. Excellent work! You've used a fundamental technique in combinatorial proofs. Here's what we discovered: Combinatorial proof strategy: instead of algebraic manipulation, we showed both sides count the same collection in two different ways. The bijection: choosing k items to include is in one-to-one correspondence with choosing n-k items to exclude. Complementary thinking: every subset has a unique complement. Including some items is the same as excluding the others. Formal structure: the map is a bijection because it is its own inverse ( f(f(S)) = S ), hence both injective and surjective. Why it matters: this identity explains the left-right symmetry of Pascal's triangle and shows up throughout discrete math and probability. Establishing a bijection to prove two sets are equal in size is a cornerstone of combinatorial reasoning — you'll use it to prove many more counting identities.

This is the written version of the interactive lesson above. See the full Intro to Proofs course.