Problem 3

Let

A(n)

denote the number of sequences

a_1\ge a_2\ge\cdots\ge 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\ge b_2\ge\cdots\ge b_m

of positive integers for which

b_1+\cdots+b_m=n

and each inequality

b_j\ge2b_{j+1}

holds (

j=1,2,\ldots,m-1

). Prove that

A(n)=B(n)

for every positive integer

n

Step 3 of 4: Marvelous arrays are determined by either sum

Previous step Next step

\text{marvelous array: rows } 2^{N-1},\ldots,2,1,\ N \text{ non-increasing, row lengths non-increasing}

Detailed analysis

Call an array marvelous if its rows are left-aligned copies of $2^{N-1},2^{N-2},\ldots,2,1$ for non-increasing values of $N$ with non-increasing row lengths. Given any type- $B$ sequence $b_1\ge\cdots\ge b_m$ , one builds a marvelous array inductively: fill $b_m$ rows with $2^{m-1},\ldots,2,1$ , then $b_{m-1}-2b_m$ further rows with $2^{m-2},\ldots,2,1$ , and so on down to $b_1-2b_2$ rows containing only the entry $1$ ; this array's column sums recover $b_1,\ldots,b_m$ exactly, and its row sums are the corresponding type- $A$ sequence. A marvelous array is determined uniquely by its row sums (obviously, since the rows are read off directly) and, by this inductive construction, equally uniquely by its column sums.