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:

11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 11 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^2 = 4. In the 7th row, all eight entries are odd. The binary representation of 7 is 111, and 2^3 = 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