Figure 1

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 Nth 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.
<http://www.math.hmc.edu/funfacts>.

