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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.