Problem 3

For an integer-coefficient polynomial

P(x)=a_0+a_1x+\cdots+a_kx^k

, let

w(P)

be the number of odd coefficients. Put

Q_i(x)=(1+x)^i

for

i=0,1,2,\ldots

. Prove that if

0\le i_1<i_2<\cdots<i_n

, then

w(Q_{i_1}+Q_{i_2}+\cdots+Q_{i_n})\ge w(Q_{i_1})

Step 1 of 4: A power-of-two block has only two odd coefficients

Previous step Next step

In plain words

A power-of-two exponent makes the binomial pattern split into a low copy and a shifted high copy, with no parity cancellation between them.

(1+x)^m\equiv1+x^m\pmod 2\quad(m=2^r)

Detailed analysis

If $m=2^r$ , every interior binomial coefficient $\binom mr$ is even. Equivalently, repeated use of $(1+x)^{2t}\equiv(1+x^2)^t\pmod2$ gives $(1+x)^m\equiv1+x^m\pmod2$ . Thus, when multiplied by a polynomial of degree less than $m$ , the two copies occupy disjoint degree ranges and $w((1+x)^mA)=2w(A)$ .