Vandermonde's identity, hockey stick, and stars and bars
Binomial coefficients satisfy a rich web of identities. The most elegant proofs are combinatorial proofs: rather than manipulating algebra, we show that both sides count the same thing in different ways. This approach often reveals the deeper structure behind the identity.
In this lesson, you will see visual proofs of Vandermonde's identity, the hockey stick identity in Pascal's triangle, and the stars-and-bars technique for distributing identical objects.
Vandermonde's identity states: C(m+n, k) = Σ C(m, j) · C(n, k-j). The combinatorial proof: choosing k people from a room of m men and n women can be broken down by how many men (j) versus women (k-j) are selected. Each split contributes C(m, j) · C(n, k-j) ways.
Choosing k people from n+m splits into: j from Group A and k-j from Group B, summed over all valid j.
Key insight: Vandermonde's identity is equivalent to the convolution identity for generating functions: (1+x)ᵐ · (1+x)ⁿ = (1+x)ᵐ⁺ⁿ. Each side's xᵏ coefficient gives one side of the identity.
The hockey stick identity says that the sum of entries along a diagonal in Pascal's triangle equals the entry one step further along the adjacent diagonal: C(r, r) + C(r+1, r) + ... + C(n, r) = C(n+1, r+1). In the triangle, the summed entries form the "shaft" and the result is the "blade" of a hockey stick. Click cells to trace your own hockey stick.
Click a cell to start, then click further down the same diagonal to extend. The bright cell is the "blade" — the sum.
Key insight: The hockey stick identity follows by telescoping Pascal's rule: C(n+1, r+1) = C(n, r+1) + C(n, r), and then expanding C(n, r+1) the same way, unwinding down the diagonal until reaching C(r, r) = 1.
How many ways can n identical objects be distributed among k distinct bins? The stars and bars method encodes each distribution as a binary string of n stars (objects) and k-1 bars (dividers). The number of such strings is C(n+k-1, k-1). This elegant technique reduces distribution problems to counting combinations.
Distributing n identical objects into k bins is equivalent to placing k-1 bars among n+k-1 positions: C(n+k-1, k-1).
Key insight: Stars and bars gives a bijection between distributions and binary strings. The formula C(n+k-1, k-1) counts the positions for the k-1 bars among n+k-1 total symbols. This also counts multisets of size n from a k-element set.