Pascal's Triangle Turns into a Fractal

Definition Pascal’s triangle has rows numbered $n = 0, 1, 2, \ldots$ from the top. Row $0$ is the single number $1$. Row $n$ has $n + 1$ entries, in positions $k = 0, 1, \ldots, n$ counted from the left, it begins and ends with $1$, and each of its other entries is the sum of the two entries just above it, its two parents. Pascal’s triangle modulo 2 replaces every entry by its remainder after division by $2$, which is $1$ for an odd entry and $0$ for an even one, and shading the cells that hold $1$ draws the picture. Its rows can be built directly, without the large numbers, because each row still begins and ends with $1$ and every other cell holds $1$ exactly when its two parents differ. The surprise is that the pattern copies itself. For every $m \ge 2$, the first $2^m$ rows, rows $0$ to $2^m - 1$, consist of three copies of the first $2^{m-1}$ rows, one at the top and two side by side below it, with an upside-down triangle of zeros between the two lower copies. Row $2^m$ is a $1$, then $2^m - 1$ zeros, then a $1$. Now draw the first $2^m$ rows inside one fixed equilateral triangle. Cut it into small triangles of side $2^{-m}$ times its side. The small triangles that point up lie in $2^m$ rows holding $1, 2, \ldots, 2^m$ of them, so each entry of rows $0$ to $2^m - 1$ can be given its own small triangle, in the same row and in the same order from left to right. The shaded cells are then exactly stage $m$ of the Sierpinski construction. As $m$ grows, these pictures approach the Sierpinski triangle, but each one is a finite stage with positive area, and only the limit is the gasket itself.

Definition The entry in row $n$ and position $k$ of Pascal’s triangle is the binomial coefficient $\binom{n}{k}$, the number of ways to choose $k$ objects from $n$ objects, for $0 \le k \le n$. The add-the-two-parents rule is Pascal’s rule

for $1 \le k \le n - 1$, together with $\binom{n}{0} = \binom{n}{n} = 1$. The parity of a whole number says whether it is even or odd. Since odd plus odd is even, even plus even is even and odd plus even is odd, a coefficient $\binom{n}{k}$ inside a row, with $1 \le k \le n - 1$, is odd exactly when one of its two parents is odd and the other is even. The parity of an entry can also be read from binary digits. By Lucas’s theorem, published by Édouard Lucas in 1878, $\binom{n}{k}$ is odd exactly when every place where the binary form of $k$ has a $1$ is also a place where the binary form of $n$ has a $1$. It follows that row $n$ has exactly $2^j$ odd entries, where $j$ is the number of ones in the binary form of $n$. The counting meaning of these numbers is the subject of Pascal’s Triangle, a Pattern Factory, and this page needs only their parity.

Definition Fix a whole number $q \ge 2$, called the modulus. Two integers $a$ and $b$ are congruent modulo $q$, written $a \equiv b \pmod{q}$, when $a - b$ is a multiple of $q$. Every integer is congruent to exactly one of the remainders $0, 1, \ldots, q - 1$, and sums and products can be found from remainders alone. If $a \equiv a'$ and $b \equiv b'$ modulo $q$, then $a + b \equiv a' + b'$ and $ab \equiv a'b'$ modulo $q$. Modulo 2 the only remainders are $0$ for even numbers and $1$ for odd numbers, and $1 + 1 \equiv 0$. Polynomials can be reduced in the same way, coefficient by coefficient. Multiplying a polynomial by $1 + x$ makes each new coefficient the sum of two neighboring old ones, which is Pascal’s rule, so the coefficients of $(1 + x)^n$ are row $n$ of Pascal’s triangle. Modulo 2,

and more generally $(u + w)^2 = u^2 + 2uw + w^2 \equiv u^2 + w^2$. Squaring again and again gives $(1 + x)^{2^m} \equiv 1 + x^{2^m}$ for every $m \ge 0$, which is why row $2^m$ is odd only at its ends. For $0 \le r < 2^m$ it then follows that

Multiplying row $r$ by $1 + x^{2^m}$ gives one copy of row $r$ in positions $0$ to $r$ and a second copy shifted $2^m$ places, in positions $2^m$ to $2^m + r$. Because $r < 2^m$ the two copies do not overlap, and the entries in positions $r + 1$ to $2^m - 1$ between them are even. This is the self-copying of Pascal’s triangle modulo 2.