Pascal’s Triangle has many surprising patterns and properties. For instance, we can ask: “how many odd numbers are in row N of Pascal’s Triangle?” For rows 0, 1, …, 20, we count:

row N: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

odd #s: 1 2 2 4 2 4 4 8 2 4 04 08 04 08 08 16 02 04 04 08 04

It appears the answer is always a power of 2. In fact, the following is true:

- THEOREM: The number of odd entries in row N of Pascal’s Triangle is 2 raised to the number of 1’s in the binary expansion of N.

Example: Since 83 = 64 + 16 + 2 + 1 has binary expansion (1010011), then row 83 has 2^{4} = 16 odd numbers.

**Presentation Suggestions:**

Prior to the class, have the students try to discover the pattern for themselves, either in HW or in group investigation.

**The Math Behind the Fact:**

Our proof makes use of the binomial theorem and modular arithmetic. The binomial theorem says that

(1+x)^{N} = SUM_{k=0 to N} (N CHOOSE k) x^{k}.

If we reduce the coefficients mod 2, then it’s easy to show by induction on N that for N >= 0,

(1+x)^{2^N} = (1+x^{2^N}) [mod 2].

Thus:

(1+x)^{10} = (1+x)^{8} (1+x)^{2} = (1+x^{8})(1+x^{2}) = 1 + x^{2} + x^{8} + x^{10} [mod 2].

Since the coefficients of these polynomials are equal [mod 2], using the binomial theorem we see that (10 CHOOSE k) is odd for k = 0, 2, 8, and 10; and it is even for all other k. Similarly, the product

(1+x)^{11} = (1+x^{8})(1+x^{2})(1+x^{1}) [mod 2]

is a polynomial containing 8=2^{3} terms, being the product of 3 factors with 2 choices in each.

In general, if N can be expressed as the sum of p distinct powers of 2, then (N CHOOSE k) will be odd for 2^{p} values of k. But p is just the number of 1’s in the binary expansion of N, and (N CHOOSE k) are the numbers in the N-th row of Pascal’s triangle. QED.

For an alternative proof that does not use the binomial theorem or modular arithmetic, see the reference. For a more general result, see Lucas’ Theorem.

**How to Cite this Page:**

Su, Francis E., et al. “Odd Numbers in Pascal’s Triangle.” *Math Fun Facts*. <https://www.math.hmc.edu/funfacts>.

**References:**

George Polya, Robert E. Tarjan and Donald R. Woods, *Notes on Introductory Combinatorics*, Birkhauser, Boston, 1983.

**Fun Fact suggested by: **

Arthur Benjamin