Putnam 1991 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{gathered}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{gathered}$$

Let $B(n)$ denote the number of $b_1 + b_2 + \cdots + b_s$ which add up to $n$, with

1. $b_1 \geq b_2 \geq \dots \geq b_s,$

2. 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

3. 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.$)