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 2^b 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 2^k−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