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

を証明せよ。

ステップ 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$ の基底場合は直ちに確認できる。