Math Fun Facts!
hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su
Subscribe to our RSS feed   or follow us on Twitter.
Get a random Fun Fact!
or
No subject limitations
Search only in selected subjects
    Algebra
    Calculus or Analysis
    Combinatorics
    Geometry
    Number Theory
    Probability
    Topology
    Other subjects
  Select Difficulty  
Enter keywords 

  The Math Fun Facts App!
 
  List All : List Recent : List Popular
  About Math Fun Facts / How to Use
  Contributors / Fun Facts Home
© 1999-2010 by Francis Edward Su
All rights reserved.

From the Fun Fact files, here is a Fun Fact at the Advanced level:

Odd Numbers in Pascal's Triangle

Figure 1
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 24 = 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 = SUMk=0 to N (N CHOOSE k) xk.
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+x2^N) [mod 2].
Thus:
(1+x)10 = (1+x)8 (1+x)2 = (1+x8)(1+x2) = 1 + x2 + x8 + x10 [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+x8)(1+x2)(1+x1) [mod 2]
is a polynomial containing 8=23 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 2p 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. <http://www.math.hmc.edu/funfacts>.

Share

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

Subjects:    combinatorics, number theory
Level:    Advanced
Fun Fact suggested by:   Arthur Benjamin
Suggestions? Use this form.
4.10
 
current
rating 		Click to rate this Fun Fact...
    *   Awesome! I totally dig it!
    *   Fun enough to tell a friend!
    *   Mildly interesting
    *   Not really noteworthy
and see the most popular Facts!
Get the Math Fun Facts
iPhone App!

Want another Math Fun Fact?

For more fun, tour the Mathematics Department at Harvey Mudd College!