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

であることを証明せよ。

ステップ 2/4: 列和は型

B

の数列をなす

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

b_j=\sum_i(\text{entry in column } j \text{ of row } i) \implies b_j\ge2b_{j+1}

詳しい解説

$b_j$ をこの配列の列 $j$ に含まれる要素の和とする。各列は右隣の列と少なくとも同じ個数の要素を持ち、 $1$ より大きい各要素は同じ行で右隣の要素のちょうど二倍であるから、 $b_j\ge2b_{j+1}$ となり、得られる数列は型 $B$ である。 $a_1+\cdots+a_k$ と $b_1+\cdots+b_m$ はいずれも配列の全要素の和に等しいので、数列 $(b_j)$ の和も $n$ である。