Binomial Identities

Combinatorics · Axiom Academy

Powerful identities derived from the binomial theorem with algebraic and combinatorial proofs 1. Sum of Binomial Coefficients Identity: The sum of all binomial coefficients in row n equals 2 n . Derivation: Start with the binomial theorem and substitute x = 1 and y = 1: Question: How many subsets does an n-element set have? Answer 1: Each element can either be included or excluded, giving 2 choices per element. Total: 2 n subsets. Answer 2: Count by size. There are C(n,0) subsets of size 0, C(n,1) subsets of size 1, ..., C(n,n) subsets of size n. Total: C(n,0) + C(n,1) + ... + C(n,n). Conclusion: Both count the same thing, so they must be equal! Identity: The alternating sum of binomial coefficients equals zero (for n > 0). Derivation: Use the binomial theorem with x = 1 and y = -1: Question: Consider an n-element set 1, 2, ..., n . How many subsets have even size minus how many have odd size? Answer 1: Pair up each subset S with its complement by toggling element 1. If S has even size, its paired subset has odd size, and vice versa. These pairs cancel out, giving 0. Answer 2: Count by size. Even sizes contribute C(n,0) + C(n,2) + C(n,4) + ..., and odd sizes contribute -(C(n,1) + C(n,3) + C(n,5) + ...). This is exactly our alternating sum. Conclusion: The alternating sum equals 0! Identity: The sum of the squares of binomial coefficients in row n equals the central coefficient in row 2n.

This is the written version of the interactive lesson above. See the full Combinatorics course.