第3题

对于整数系数多项式

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

，记

w(P)

为奇数系数的个数。令

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

（

i=0,1,2,\ldots

）。证明：若

0\le i_1<i_2<\cdots<i_n

，则

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

。

第 4/4 步：完成归纳

通俗地说

分割不会损失超过子问题已控制的奇系数，归纳便把所需下界带回原来的总和。

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

详细分析

多项式 $A$ 含有最小项 $Q_{i_1}$ ，且最大指标 $i_r<m\le i_n$ ，故由归纳假设 $w(A)\ge w(Q_{i_1})$ 。第 3 步给出 $w(Q)\ge w(A)$ ，归纳完成。最大指标为 $0$ 或 $1$ 的基础情形直接可见。