第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})

。

第 2/4 步：最小指标较大时平移所有指标

上一步下一步

通俗地说

当所有指标至少为 $m$ 时，从每一项中剥去同一个二的幂层；归纳问题只是缩小尺度后的同一幅图景。

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

详细分析

对 $i_n$ 作强归纳。取最大二的幂 $m$ ，使 $m\le i_n<2m$ 。若 $i_1\ge m$ ，写成 $Q_{i_j}=(1+x)^mQ_{i_j-m}$ ，令 $B=\sum_jQ_{i_j-m}$ 。平移后的最大指标小于 $i_n$ ，故由归纳 $w(Q_{i_1-m})\le w(B)$ 。由第 1 步两边都加倍，得 $w(Q_{i_1})=2w(Q_{i_1-m})\le2w(B)=w(\sum_jQ_{i_j})$ 。