Mathematical Behavior of Pascal's Triangle (mod 2)

Lucas's Theorem

Let p be a prime number, and let r and c be written in p-ary notation

Then

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ⁿ rows, both r and c are less than 2ⁿ. Therefore they can be written in binary notation as

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

But then by Lucas's Theorem, we have

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ⁿ-1. The next row therefore has r = 2ⁿ and columns 0 <= c <= 2ⁿ. 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

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ⁿ⁺¹-1 and

Back to Pascal's Triangle (mod 2)

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