Parity Devil

How many coefficients are odd in the expansion of ( x + 1 ) 1000 (x+1)^{1000} ?


The answer is 64.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Pi Han Goh
Oct 28, 2016

By binomial expansion, ( x + 1 ) 1000 = ( 1000 0 ) x 1000 + ( 1000 1 ) x 999 + ( 1000 2 ) x 998 + + ( 1000 1000 ) x 0 (x+1)^{1000} = \dbinom{1000}0 x^{1000} + \dbinom{1000}1 x^{999} + \dbinom{1000}2 x^{998} + \cdots + \dbinom{1000}{1000} x^0 .

So we want to find the number of odd numbers among the set of numbers, { ( 1000 0 ) , ( 1000 1 ) , ( 1000 2 ) , , ( 1000 1000 ) } \left \{\dbinom{1000}0 , \dbinom{1000}1 , \dbinom{1000}2 , \ldots, \dbinom{1000}{1000} \right \} .

Referencing Lucas' theorem :

In particular, ( m n ) \binom{m}{n} is divisible by p p if and only if at least one of the base- p p digits of n n is greater than the corresponding base- p p digit of m m .

If we rewrite 1000 in base 2, we have 100 0 10 = 111110100 0 2 1000_{10} = 1111101000_2 . Since there's six 1's in its binary representation, the answer is 2 6 = 64 2^6 = \boxed{64} .

Or one could equivalently use Kummer's theorem .

Daksh A Agarwal - 4 years, 7 months ago

Log in to reply

Yup! Kummer's theorem = special extension/case of Lucas' theorem

Pi Han Goh - 4 years, 7 months ago

Since there's six 1's...

is what you want.

Wen Z - 4 years, 7 months ago

Log in to reply

Whoops, fixed!

Pi Han Goh - 4 years, 7 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...