Mudd Math Fun Facts!
hosted by the Harvey Mudd College Math Department created, authored and ©1999-2007 by Francis Su
You can now subscribe to our RSS feed to get the latest Fun Facts!
Get a random Fun Fact!
No subject limitations
Search only in selected subjects
    Algebra
    Calculus or Analysis
    Combinatorics
    Geometry
    Number Theory
    Probability
    Topology
    Other subjects
  Select Difficulty  
Enter keywords 

  List All : List Recent : List Popular
  About Math Fun Facts / How to Use
  Contributors / Fun Facts Home
© 1999-2007 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 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." Mudd Math Fun Facts. <http://www.math.hmc.edu/funfacts>.

Bookmark this page on: | Digg this! | Del.icio.us | Technorati | Reddit | Fark | Squidoo | Furl | Blinklist | Yahoo MyWeb | Google | Stumbleupon |

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.30
 
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!

Want another Math Fun Fact?

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