Binomial Coefficient Identities — Mathematics Knowledge System

Overview

Binomial coefficients C(n,k) satisfy a rich family of identities beyond their basic definition, discovered through algebraic manipulation, generating functions, or combinatorial (bijective) arguments. Classic examples include Pascal's rule, the symmetry identity, the sum over a row equaling 2ⁿ, Vandermonde's identity for combining two rows, and the hockey stick identity for summing a diagonal. These identities are workhorses throughout combinatorics, probability, and computer science, often turning an intractable sum into a closed form.

Intuition

Each identity has a counting story behind it. Pascal's rule splits subsets by whether a fixed element is included or not. The row-sum identity counts all subsets of an n-set two ways: directly (2ⁿ choices, in/out for each element) and by size (summing C(n,k) over all sizes k). Vandermonde's identity counts choosing k people from a group split into m men and n women by splitting the choice into 'i men and k-i women' for each possible i. Seeing these as counting arguments — rather than algebra to memorize — makes it easy to derive new identities on the fly.

Formal Definition

Definition

Key identities involving binomial coefficients:

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

Pascal's rule

\sum_{k=0}^{n} \binom{n}{k} = 2^n

Row sum

\binom{m+n}{k} = \sum_{i=0}^{k} \binom{m}{i}\binom{n}{k-i}

Vandermonde's identity

\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}

Hockey stick identity

Worked Examples

Compute each term.
$\binom{3}{0}=1,\ \binom{3}{1}=3,\ \binom{3}{2}=3,\ \binom{3}{3}=1$
Sum them.
$1+3+3+1 = 8 = 2^3$

Answer: 8 = 2³, confirming the identity.

Practice Problems

Difficulty 3/10

Use Pascal's rule to compute C(5,2) from C(4,1) and C(4,2).

Difficulty 5/10

Use the hockey stick identity to compute C(2,2)+C(3,2)+C(4,2)+C(5,2).

Difficulty 4/10

Compute the sum of row n=4 of Pascal's triangle directly and confirm it equals 2⁴.

Quiz

Summary

Pascal's rule, symmetry, and the row-sum-to-2ⁿ identity are the foundational binomial coefficient relations.
Vandermonde's identity and the hockey stick identity let you combine or telescope sums of binomial coefficients into closed forms.
Most identities have both an algebraic proof and a combinatorial (counting) proof, and the counting proof is usually more illuminating.

References

WebsiteWikipedia — Binomial coefficient