{"id":515,"date":"2019-06-29T22:07:08","date_gmt":"2019-06-29T22:07:08","guid":{"rendered":"http:\/\/funfacts.104.42.120.246.xip.io\/?page_id=515"},"modified":"2019-12-09T22:12:04","modified_gmt":"2019-12-09T22:12:04","slug":"odd-numbers-in-pascals-triangle","status":"publish","type":"page","link":"https:\/\/math.hmc.edu\/funfacts\/odd-numbers-in-pascals-triangle\/","title":{"rendered":"Odd Numbers in Pascal&#8217;s Triangle"},"content":{"rendered":"\n<div class=\"wp-block-image\"><figure class=\"alignright\"><img loading=\"lazy\" decoding=\"async\" width=\"155\" height=\"139\" data-attachment-id=\"1548\" data-permalink=\"https:\/\/math.hmc.edu\/funfacts\/odd-numbers-in-pascals-triangle\/30001-4-5-1\/\" data-orig-file=\"https:\/\/math.hmc.edu\/funfacts\/wp-content\/uploads\/sites\/4\/2019\/12\/30001.4-5.1.gif\" data-orig-size=\"155,139\" data-comments-opened=\"1\" data-image-meta=\"{&quot;aperture&quot;:&quot;0&quot;,&quot;credit&quot;:&quot;&quot;,&quot;camera&quot;:&quot;&quot;,&quot;caption&quot;:&quot;&quot;,&quot;created_timestamp&quot;:&quot;0&quot;,&quot;copyright&quot;:&quot;&quot;,&quot;focal_length&quot;:&quot;0&quot;,&quot;iso&quot;:&quot;0&quot;,&quot;shutter_speed&quot;:&quot;0&quot;,&quot;title&quot;:&quot;&quot;,&quot;orientation&quot;:&quot;0&quot;}\" data-image-title=\"30001.4-5.1\" data-image-description=\"\" data-image-caption=\"\" data-medium-file=\"https:\/\/math.hmc.edu\/funfacts\/wp-content\/uploads\/sites\/4\/2019\/12\/30001.4-5.1.gif\" data-large-file=\"https:\/\/math.hmc.edu\/funfacts\/wp-content\/uploads\/sites\/4\/2019\/12\/30001.4-5.1.gif\" src=\"https:\/\/math.hmc.edu\/funfacts\/wp-content\/uploads\/sites\/4\/2019\/12\/30001.4-5.1.gif\" alt=\"\" class=\"wp-image-1548\"\/><\/figure><\/div>\n\n\n\n<p>Pascal&#8217;s Triangle\u00a0has many surprising patterns and properties. For instance, we can ask: &#8220;how many odd numbers are in row N of Pascal&#8217;s Triangle?&#8221; For rows 0, 1, &#8230;, 20, we count:<\/p>\n\n\n\n<p>row N: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20&nbsp;<br>odd #s: 1 2 2 4 2 4 4 8 2 4 04 08 04 08 08 16 02 04 04 08 04<\/p>\n\n\n\n<p>It appears the answer is always a power of 2. In fact, the following is true:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li> THEOREM: The number of odd entries in row N of Pascal&#8217;s Triangle is 2 raised to the number of 1&#8217;s in the binary expansion of N. <\/li><\/ul>\n\n\n\n<p>Example: Since 83 = 64 + 16 + 2 + 1 has binary expansion (1010011), then row 83 has 2<sup>4<\/sup>&nbsp;= 16 odd numbers.<\/p>\n\n\n\n<p><strong>Presentation&nbsp;Suggestions:<\/strong><br>Prior to the class, have the students try to discover the pattern for themselves, either in HW or in group investigation.<\/p>\n\n\n\n<p><strong>The\u00a0Math\u00a0Behind\u00a0the\u00a0Fact:<\/strong><br>Our proof makes use of the binomial theorem and modular arithmetic. The binomial theorem says that<\/p>\n\n\n\n<p style=\"text-align:center\">(1+x)<sup>N<\/sup>\u00a0= SUM<sub>k=0 to N<\/sub>\u00a0(N CHOOSE k) x<sup>k<\/sup>. <\/p>\n\n\n\n<p>If we reduce the coefficients mod 2, then it&#8217;s easy to show by induction on N that for N >= 0,<\/p>\n\n\n\n<p style=\"text-align:center\">(1+x)<sup>2^N<\/sup>\u00a0= (1+x<sup>2^N<\/sup>) [mod 2].<\/p>\n\n\n\n<p>Thus: <\/p>\n\n\n\n<p style=\"text-align:center\">(1+x)<sup>10<\/sup>\u00a0= (1+x)<sup>8<\/sup>\u00a0(1+x)<sup>2<\/sup>\u00a0= (1+x<sup>8<\/sup>)(1+x<sup>2<\/sup>) = 1 + x<sup>2<\/sup>\u00a0+ x<sup>8<\/sup>\u00a0+ x<sup>10<\/sup>\u00a0[mod 2].<\/p>\n\n\n\n<p>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<\/p>\n\n\n\n<p style=\"text-align:center\">(1+x)<sup>11<\/sup>\u00a0= (1+x<sup>8<\/sup>)(1+x<sup>2<\/sup>)(1+x<sup>1<\/sup>) [mod 2]<\/p>\n\n\n\n<p>is a polynomial containing 8=2<sup>3<\/sup>\u00a0terms, being the product of 3 factors with 2 choices in each.<\/p>\n\n\n\n<p>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<sup>p<\/sup>&nbsp;values of k. But p is just the number of 1&#8217;s in the binary expansion of N, and (N CHOOSE k) are the numbers in the N-th row of Pascal&#8217;s triangle. QED.<\/p>\n\n\n\n<p>For an alternative proof that does not use the\u00a0binomial theorem\u00a0or modular arithmetic, see the reference. For a more general result, see\u00a0Lucas&#8217; Theorem.<\/p>\n\n\n\n<p><strong>How to Cite this Page:<\/strong>&nbsp;<br>Su, Francis E., et al. &#8220;Odd Numbers in Pascal&#8217;s Triangle.&#8221;&nbsp;<em>Math Fun Facts<\/em>. &lt;http:\/\/www.math.hmc.edu\/funfacts&gt;.<\/p>\n\n\n\n<p><strong>References:<\/strong><br>George Polya, Robert E. Tarjan and Donald R. Woods, <em>Notes on Introductory Combinatorics<\/em>, Birkhauser, Boston, 1983.<\/p>\n\n\n\n<p><strong>Fun Fact suggested by:   <\/strong><br>Arthur Benjamin<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Pascal&#8217;s Triangle\u00a0has many surprising patterns and properties. For instance, we can ask: &#8220;how many odd numbers are in row N&#46;&#46;&#46;<\/p>\n","protected":false},"author":7,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"tags":[57,9,3,10,12,169,15],"class_list":["post-515","page","type-page","status-publish","hentry","tag-advanced","tag-combinatorics","tag-easy","tag-numtheory","tag-other","tag-patterns","tag-polynomial"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/515","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/comments?post=515"}],"version-history":[{"count":6,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/515\/revisions"}],"predecessor-version":[{"id":1549,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/515\/revisions\/1549"}],"wp:attachment":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/media?parent=515"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/tags?post=515"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}