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 4 of 4: Conclude the bijection

Previous step Next step

A(n)=B(n)

Detailed analysis

The row-sum map (type $A$ to type $B$ , via reading off column sums of the array built from the rows) and the column-sum map (type $B$ to type $A$ , via reading off row sums of the marvelous array built from the columns) are mutually inverse, since a marvelous array is uniquely recovered from either its row sums or its column sums. Hence these maps give a bijection between type- $A$ sequences summing to $n$ and type- $B$ sequences summing to $n$ , so $A(n)=B(n)$ for every positive integer $n$ .