Odd numbers in Pascal’s triangle

Here’s an interesting theorem I ran across recently.

The number of odd integers in the nth row of Pascal’s triangle equals 2b where b is the number of 1’s in the binary representation of n.

Here are the first few rows of Pascal’s triangle: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 .

We count rows starting from 0, so for n at least 1, the nth row has n in the second column.

Notice, for example, that on the 6th four of the entries are odd: 1, 15, 15, 1.

The binary representation of 6 is 110, so b = 2, and 2² = 4.

In the 7th row, all eight entries are odd.

The binary representation of 7 is 111, and 2³ = 8.

There are a couple quick corollaries to the theorem above.

First, the number of odd numbers in the nth row of Pascal’s triangle is always a power of 2.

Second, in row 2k-1 – 1, all entries are odd.

This post is a slightly expanded version of a Twitter thread I posted on @AlgebraFact this weekend.

More on Pascal’s triangle Pascal’s triangle and Fermat’s little theorem Distribution of numbers in Pascal’s triangle The Star of David theorem.

Leave a Reply