Larry Riddle, Agnes Scott College

The basis for the proof is the following old theorem given by Edouard Lucas in 1890.

**Lucas's Theorem**- Let p be a prime number, and let r and c be written in p-ary notation
$$\begin{array}{l} r = {r_k} \cdots {r_2}{r_1}{r_0} = {r_0} + {r_1}p + {r_2}{p^2} + \cdots + {r_k}{p^k} \qquad (0 \le {r_i} \lt p) \\ c = {c_k} \cdots {c_2}{c_1}{c_0} = {c_0} + {c_1}p + {c_2}{p^2} + \cdots + {c_k}{p^k} \qquad (0 \le {c_i} \lt p) \\ \end{array}$$

Then

$$\left( {\begin{array}{*{20}{c}} r \\ c \\ \end{array}} \right) = \left( {\begin{array}{*{20}{c}} {{r_0}} \\ {{c_0}} \\ \end{array}} \right)\left( {\begin{array}{*{20}{c}} {{r_1}} \\ {{c_1}} \\ \end{array}} \right)\left( {\begin{array}{*{20}{c}} {{r_1}} \\ {{c_1}} \\ \end{array}} \right) \cdots \left( {\begin{array}{*{20}{c}} {{r_k}} \\ {{c_k}} \\ \end{array}} \right)(\bmod p)$$

We take here the standard convention that the binomial coefficient (r,c)=0 if c > r.

To look at Pascal's triangle (mod 2), take p=2. Let's take a look at the
binomial coefficient (r,c) in row r and column c of P_{n}.
Because P_{n} has only
2^{n} rows,
both r and c are less than 2^{n}. Therefore
they can be written in binary notation as

$$\begin{array}{l} r = {r_{n-1}} \cdots {r_2}{r_1}{r_0} \qquad (0 \le {r_i} \lt 2) \\ c = {c_{n-1}} \cdots {c_2}{c_1}{c_0} \qquad (0 \le {c_i} \lt 2) \\ \end{array}$$

Also, since P_{n} has a total of 2^{n} rows,
and has 2^{n} columns in the last row, the binomial
coefficient in the equivalent position in the lower left triangular corner
of P_{n+1} is (2^{n}+r, c) and the binomial coefficient
in the equivalent position in the lower right triangular corner is
(2^{n}+r, 2^{n}+c).

But then by Lucas's Theorem, we have

$$ \begin{align} \left( {\begin{array}{*{20}c} {2^n + r} \\ c \\ \end{array}} \right)\,(\bmod 2) &= \left( {\begin{array}{*{20}c} {1{\kern 1pt} {\kern 1pt} r_{ n - 1} \cdots {\kern 1pt} {\kern 1pt} {\kern 1pt} r_{ 0} } \\ {0{\kern 1pt} {\kern 1pt} c_{ n - 1} \cdots {\kern 1pt} {\kern 1pt} {\kern 1pt} c_{ 0} } \\ \end{array}} \right)\,(\bmod 2) = \left( {\begin{array}{*{20}c} 1 \\ 0 \\ \end{array}} \right)\left( {\begin{array}{*{20}c} {r_{ 0} } \\ {c_{ 0} } \\ \end{array}} \right) \cdots \left( {\begin{array}{*{20}c} {r_{ n - 1} } \\ {c_{ n - 1} } \\ \end{array}} \right)\;(\bmod 2) \\ &= \left( {\begin{array}{*{20}c} {r_{ 0} } \\ {c_{ 0} } \\ \end{array}} \right) \cdots \left( {\begin{array}{*{20}c} {r_{ n - 1} } \\ {c_{ n - 1} } \\ \end{array}} \right)\;(\bmod 2) = \left( {\begin{array}{*{20}c} r \\ c \\ \end{array}} \right)\,(\bmod 2) \\ \end{align} $$

$$ \begin{align} \left( {\begin{array}{*{20}c} {2^n + r} \\ {2^n + c} \\ \end{array}} \right)\,(\bmod 2) &= \left( {\begin{array}{*{20}c} {1{\kern 1pt} {\kern 1pt} r_{{\kern 1pt} n - 1} \cdots {\kern 1pt} {\kern 1pt} {\kern 1pt} r_{ 0} } \\ {1{\kern 1pt} {\kern 1pt} c_{ n - 1} \cdots {\kern 1pt} {\kern 1pt} {\kern 1pt} c_{ 0} } \\ \end{array}} \right)\,(\bmod 2) = \left( {\begin{array}{*{20}c} 1 \\ 1 \\ \end{array}} \right)\left( {\begin{array}{*{20}c} {r_{ 0} } \\ {c_{ 0} } \\ \end{array}} \right) \cdots \left( {\begin{array}{*{20}c} {r_{ n - 1} } \\ {c_{ n - 1} } \\ \end{array}} \right)\;(\bmod 2) \\ &= \left( {\begin{array}{*{20}c} {r_{ 0} } \\ {c_{ 0} } \\ \end{array}} \right) \cdots \left( {\begin{array}{*{20}c} {r_{ n - 1} } \\ {c_{ n - 1} } \\ \end{array}} \right)\;(\bmod 2) = \left( {\begin{array}{*{20}c} r \\ c \\ \end{array}} \right)\,(\bmod 2) \\ \end{align} $$

Therefore all three binomial coefficients have the same value (mod 2) and hence would have the same color in Pascal's triangle (mod 2). This proves the first part of the recursive behavior of Pascal's triangle.

To prove the second part, we must show that the three equivalent corner
triangles of P_{n+1} surround a triangle of even numbers. Again we
appeal to Lucas's Theorem. The last row of P_{n} corresponds to
r = 2^{n}-1. The next row therefore has r = 2^{n} and
columns 0 <= c <= 2^{n}. The first and last values in
this row are equal to 1. These are the top squares in the lower left and
lower right triangular corners, respectively. For all the other columns
in the row, however, at least one
binary digit in c will be a 1 and therefore for 1 ≤ c ≤ 2^{n}−1

$$ \begin{align} \left( {\begin{array}{*{20}c} {2^n } \\ c \\ \end{array}} \right)\, &= \left( {\begin{array}{*{20}c} {1{\kern 1pt} {\kern 1pt} 0 \cdots {\kern 1pt} {\kern 1pt} 0} \\ {0{\kern 1pt} c_{n - 1} {\kern 1pt} \cdots {\kern 1pt} {\kern 1pt} c_0 } \\ \end{array}} \right)\, \\ &= \left( {\begin{array}{*{20}c} 1 \\ 0 \\ \end{array}} \right)\left( {\begin{array}{*{20}c} 0 \\ {c _{n - 1} } \\ \end{array}} \right) \cdots \left( {\begin{array}{*{20}c} 0 \\ 1 \\ \end{array}} \right) \cdots \left( {\begin{array}{*{20}c} 0 \\ {c_0 } \\ \end{array}} \right)\;(\bmod 2) = 0 \\ \end{align} $$

since (0,1) = 0. Hence this row starts and ends with an odd number, but all the remaining numbers are even.

What happens in the next row? Recall that
(r+1,c) = (r,c) + (r,c-1). Therefore each number in the next row is the
sum of two adjacent numbers in the current row. But the sum of an odd and
an even number is odd, and the sum of two even numbers is even. Therefore
the string of even numbers produces a new string of even numbers bounded
on both ends by an odd number, with the new string of even numbers
containing one less value than the previous row. Each time we move to the
next row we reduce the string of even numbers by 1. By the time we reach
the last row of P_{n+1}, we have eliminated all the even numbers.
Thus we have produced the inner triangle of even numbers. The last row
will consist of all odd numbers since for this row r = 2^{n+1}-1
and

$$ \left( {\begin{array}{*{20}c} {2^{n + 1} - 1} \\ c \\ \end{array}} \right)\, = \left( {\begin{array}{*{20}c} {1{\kern 1pt} 1 \cdots 11} \\ {{\kern 1pt} c_n {\kern 1pt} \cdots {\kern 1pt} {\kern 1pt} {\kern 1pt} c_0 } \\ \end{array}} \right)\, = \left( {\begin{array}{*{20}c} 1 \\ {c_n } \\ \end{array}} \right) \cdots \left( {\begin{array}{*{20}c} 1 \\ {c_0 } \\ \end{array}} \right)\;(\bmod 2) = 1 $$

- Fine, N.J. "Binomial coefficients modulo a prime," Mathematical Association of America Monthly, December 1947, 589-592.
- Stewart, Ian. "Four encounters with Sierpinski's Gasket," Mathematical Intelligencer 17 (1995), No. 1, 52-64.
- Sven, Marta. "Divisibility—With Visibility," Mathematical Intelligencer 10 (1988), No. 2, 56-64.