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 4 of 4: Finish the induction

Previous step Next step

In plain words

The split never loses more odd coefficients than the smaller subproblem already accounted for; induction then carries the desired lower bound back to the original sum.

w(Q)\ge w(A)\ge w(Q_{i_1})

Detailed analysis

The polynomial $A$ contains the smallest term $Q_{i_1}$ and has maximum index $i_r<m\le i_n$ , so the induction hypothesis gives $w(A)\ge w(Q_{i_1})$ . Step 3 gives $w(Q)\ge w(A)$ , completing the induction. The base case (largest index $0$ or $1$ ) is immediate.