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 2 of 4: Shift every index when the smallest index is high

Previous step Next step

In plain words

When every index is at least $m$ , remove the same power-of-two layer from every term; the induction problem is the same picture at a smaller scale.

Q_{i_1}+\cdots+Q_{i_n}=(1+x)^m(B)\quad(i_1\ge m)

Detailed analysis

Use strong induction on $i_n$ . Let $m$ be the largest power of two with $m\le i_n<2m$ . If $i_1\ge m$ , write $Q_{i_j}=(1+x)^mQ_{i_j-m}$ and let $B=\sum_jQ_{i_j-m}$ . All shifted indices have largest index less than $i_n$ , so induction gives $w(Q_{i_1-m})\le w(B)$ . Step 1 doubles both sides: $w(Q_{i_1})=2w(Q_{i_1-m})\le2w(B)=w(\sum_jQ_{i_j})$ .