2017 APMO 第 3 题

Let $A(n)$ denote the number of sequences $a_{1} \geq a_{2} \geq \ldots \geq a_{k}$ of positive integers for which $a_{1}+\cdots+a_{k}=n$ and each $a_{i}+1$ is a power of two $(i=1,2, \ldots, k)$. Let $B(n)$ denote the number of sequences $b_{1} \geq b_{2} \geq \ldots \geq b_{m}$ of positive integers for which $b_{1}+\cdots+b_{m}=n$ and each inequality $b_{j} \geq 2 b_{j+1}$ holds $(j=1,2, \ldots, m-1)$.

Prove that $A(n)=B(n)$ for every positive integer $n$.

令 $A(n)$ 表示正整数序列 $a_{1} \geq a_{2} \geq \ldots \geq a_{k}$ 的数量，其中 $a_{1}+\cdots+a_{k}=n$ 且每个 $a_{i}+1$ 是 2 $(i=1,2, \ldots, k)$ 的幂。令 $B(n)$ 表示正整数序列 $b_{1} \geq b_{2} \geq \ldots \geq b_{m}$ 的数量，其中 $b_{1}+\cdots+b_{m}=n$ 且每个不等式 $b_{j} \geq 2 b_{j+1}$ 包含 $(j=1,2, \ldots, m-1)$。

证明对于每个正整数 $n$，$A(n)=B(n)$。