Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Counting Odd Coefficients


Date: 05/27/98 at 20:12:23
From: Ehsan
Subject: Number Theory

Hi. 

The question is: If (1+x)^100 is multiplied out, how many of the 
coefficients are odd? How would you generalize?

The way I tried to tackle the problem was that I set the equation 
equal to ((1+x)^4)^25. Then I multiplied out the inner part and found 
that there was only one odd coefficient (x^4 - 2x^2 + 2x - 1). I don't 
know if there will still be only one odd coefficient as a final answer 
or there will be 25 of them. 


Date: 06/04/98 at 23:12:24
From: Doctor Bob
Subject: Re: Number Theory

Hello Ehsan,

I see some problems and also a good idea in what you have written so 
far. You appear to be saying that (1+x)^4 multiplied out is 
x^4 - 2x^2 + 2x - 1. However, I get:

   (1+x)^4 = 1 + 4x + 6x^2 + 4x^3 + x^4.

Another question has to do with what is counted as a "coefficient." 
The most usual use of the word would count the constant term as a 
coefficient. Thus, 8x^2 + 5x + 3 has three coefficients, namely 8, 5, 
and 3. Thus one would say that there are three odd coefficients in 
this polynomial. The best way that I can approach your problem works 
by counting the constant term as a coefficient. I suggest that we 
proceed by assuming that. If you want the other answer, you can adjust 
at the end by reducing the number of odd coefficients by 1 if the 
constant term happens to be even.

Now to start you on a solution:

Think about what happens when you do basic arithmetic with odd and 
even numbers. For example, odd * odd = odd, even * odd = even, 
odd + odd = even, and so on. 

You can use this to multiply polynomials when you only care whether 
the coefficients are even or odd. For example:

   (1 + 3x + 4x^2)(2 - 4x + x^2)     would be 
   (odd + odd*x + even*x^2)(even + even*x + odd*x^2)
 
That is long to write, so let's write 0 for even and 1 for odd. All 
the addition and multiplication rules two paragraphs above work just 
as you add and multiply 0's and 1's EXCEPT that 1 + 1 = 2 while 
odd + odd = even. Because of this, every time we add 1 and 1, let's 
write 1 + 1 [=] 0 (to mean "even"). I put the [] around = to denote 
that this is not ordinary equality, just equality of even-ness and 
odd-ness.

(Note: Dr. Timothy suggests that this notation may not be understood. 
Here are some examples of [=]:

   2x^2 +3x +4 [=] x   (odds become 1 and evens become 0)
   5x^4 + 4x^2 -2x + 7 [=] x^4 + 1    

End of note.)

Let me demonstrate this with (1 + 3x + 4x^2)(2 - 4x + x^2). 
We would write:

   (1 + 1x + 0x^2)(0 + 0x + 1x^2) 
      = 1*0+1*0x+1*1x^2+1*0x+1*0x^2+1*1x^3+0*0x^2+0*0x^3+0*1x^4
     [=] 0 + 0x + 1x^2 + 0x + 0x^2 + 1x^3 + 0x^2 + 0x^3 + 0x^4
     [=] 0 + 0x + 1x^2 + 1x^3 + 0x^4

Thus, you can see that the result has 2 odd coefficients. You can just 
omit any term with a zero coefficient because of the rules for even 
and odd. Then a much shorter version is: (1 + x)(x^2) [=] x^2 + x^3. 

Now to your problem. Your good idea was to look at (1+x)^4 and then 
use exponent rules. Let's start by looking at (1+x)^2. We get:

   (1+x)^2 = (1+x)(1+x) 
           = 1 + 1x + 1x + 1x^2  
          [=] 1 + 0x + 1x^2  
          [=] 1 + x^2

Then:

   (1+x)^4 = (1+x)^2*(1+x)^2 
          [=] (1+x^2) * (1+x^2)
          [=] 1 + 1x^2 + 1x^2 + 1x^4
          [=] 1 + 0x^2 + 1x^4
          [=] 1 + x^4 

Thus, (1+x)^4 has two odd coefficients.

My final hint is for you to use this idea to get similar results for 
(1+x)^32, (1+x)^96, and finally (1+x)^100.

Whew! That looks a little complicated, but the idea is not so hard 
once you catch on. Persevere!

-Doctor Bob,  The Math Forum
Check out our web site! http://mathforum.org/dr.math/   
    
Associated Topics:
High School Number Theory
High School Polynomials

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/