第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$ ，各行长度不增。