Binomial Coefficients Modulo 2 and Sierpiński's Triangle
What You'll Learn
You'll discover how Pascal's Triangle reveals a stunning fractal pattern when you color entries based on whether they're odd or even.
The Core Idea
Take Pascal's Triangle—that familiar triangular array of binomial coefficients—and apply a simple rule: color each entry black if it's odd, white if it's even (or equivalently, examine each binomial coefficient modulo 2).
What emerges is breathtaking: the pattern resembles Sierpiński's Triangle, one of mathematics' most famous fractals.
Why This Happens
The key lies in Lucas's Theorem for prime p = 2. When you compute C(n,r) mod 2, the coefficient is odd (≡ 1 mod 2) if and only if, in binary representation, every bit of r is less than or equal to the corresponding bit of n. In other words, r is a "binary submask" of n.
This binary relationship creates the self-similar, fractal structure. Each triangular "block" of Pascal's Triangle mirrors the overall pattern at smaller scales.
The Visual Pattern
Start coloring:
- Row 0: 1 (odd) → black
- Row 1: 1, 1 (both odd) → black, black
- Row 2: 1, 2, 1 (odd, even, odd) → black, white, black
- Row 3: 1, 3, 3, 1 (all odd) → all black
As you continue, triangular "holes" (white regions) appear within larger black triangles, repeating infinitely—the hallmark of Sierpiński's Triangle.
The Connection
Powers of 2 are especially important: Row 2^k consists entirely of odd numbers (all 1s in the simplified mod-2 view), creating the boundaries of the self-similar structure.
Key Takeaway: Coloring Pascal's Triangle by parity reveals Sierpiński's Triangle, demonstrating how number theory, combinatorics, and fractal geometry beautifully intersect through the binary structure of binomial coefficients.