第3問

整数係数多項式

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

に対し、奇数である係数の個数を

w(P)

とする。

i=0,1,2,\ldots

に対して

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

とおく。

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$ なら、全項から同じ 2 の冪の層を取り除く。帰納法の問題は小さい尺度で 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$ を満たす最大の 2 の冪をとる。 $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で両辺を2倍すれば $w(Q_{i_1})=2w(Q_{i_1-m})\le2w(B)=w(\sum_jQ_{i_j})$ となる。