第3問

A(n)

を、

a_1+\cdots+a_k=n

かつ各

a_i+1

（

i=1,2,\ldots,k

）が二のべきであるような正整数の数列

a_1\ge a_2\ge\cdots\ge a_k

の個数とする。

B(n)

を、

b_1+\cdots+b_m=n

かつ各不等式

b_j\ge2b_{j+1}

（

j=1,2,\ldots,m-1

）が成り立つような正整数の数列

b_1\ge b_2\ge\cdots\ge b_m

の個数とする。すべての正整数

n

に対して

A(n)=B(n)

であることを証明せよ。

ステップ 1/4: 型

A

の数列を左揃え配列に展開する

前のステップ次のステップ

a_i=2^{N_i-1}+2^{N_i-2}+\cdots+2^1+2^0

詳しい解説

各項が $a_i+1=2^{N_i}$ （ $N_i$ はある正整数）を満たす数列を型 $A$ 、連続する項について $b_j\ge2b_{j+1}$ を満たす数列を型 $B$ と呼ぶ。型 $A$ の数列 $a_1\ge\cdots\ge a_k$ が与えられたとき、恒等式 $2^{N}-1=2^{N-1}+\cdots+2+1$ を用いて各 $a_i=2^{N_i-1}+\cdots+2^1+2^0$ と展開し、これらの二べきを、行 $i$ が $a_i$ の展開を保持するように左揃え配列として書く； $a_1\ge\cdots\ge a_k$ より行の長さは非増加である。