1991 Putnam A6

Let $A(n)$ denote the number of sums of positive integers
$$a_1 + a_2 + \cdots + a_r$$
which add up to $n$ with
\begin{gather*}
a_1 > a_2 + a_3, a_2 > a_3 + a_4, \ldots, \\
a_{r-2} > a_{r-1} + a_r, a_{r-1} > a_r.
\end{gather*}
Let $B(n)$ denote the number of $b_1 + b_2 + \cdots + b_s$ which add up
to $n$, with

\item $b_1 \geq b_2 \geq \dots \geq b_s,$
\item each $b_i$ is in the sequence $1, 2, 4, \dots, g_j, \dots$
defined by $g_1 = 1$, $g_2 = 2$, and $g_j = g_{j-1} + g_{j-2} + 1,$ and
\item if $b_1 = g_k$ then every element in $\{1, 2, 4, \dots, g_k\}$
appears at least once as a $b_i$.

Prove that $A(n) = B(n)$ for each $n \geq 1$.

(For example, $A(7) = 5$ because the relevant sums are $7, 6+1, 5+2, 4+3,

4+2+1,$and$B(7) = 5$because the relevant sums are$4+2+1, 2+2+2+1,

2+2+1+1+1, 2+1+1+1+1+1, 1+1+1+1+1+1+1.$)

令 $A(n)$ 表示正整数的和的数量

$$

a_1 + a_2 + \cdots + a_r

$$

总计为 $n$

\开始{收集*}

a_1 > a_2 + a_3, a_2 > a_3 + a_4, \ldots, \\

a_{r-2} > a_{r-1} + a_r, a_{r-1} > a_r。

\结束{聚集*}

设 $B(n)$ 表示 $b_1 + b_2 + \cdots + b_s$ 加起来的数量

到 $n$，其中

\item $b_1 \geq b_2 \geq \dots \geq b_s,$

\item 每个 $b_i$ 都在序列 $1, 2, 4, \dots, g_j, \dots$ 中

由 $g_1 = 1$、$g_2 = 2$ 和 $g_j = g_{j-1} + g_{j-2} + 1,$ 定义

\item 如果 $b_1 = g_k$ 则 $\{1, 2, 4, \dots, g_k\}$ 中的每个元素

作为 $b_i$ 至少出现一次。

证明对于每个 $n \geq 1$，$A(n) = B(n)$。

(例如，$A(7) = 5$，因为相关总和为 $7、6+1、5+2、4+3，

4+2+1,$和$B(7) = 5$因为相关总和是$4+2+1, 2+2+2+1,

2+2+1+1+1, 2+1+1+1+1+1, 1+1+1+1+1+1+1.$)