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
Math Forum Home || Math Library || Quick Reference || Math Forum Search