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 2 of 4: Column sums form a type-

B

sequence

Previous step Next step

b_j=\sum_i(\text{entry in column } j \text{ of row } i) \implies b_j\ge2b_{j+1}

Detailed analysis

Let $b_j$ be the sum of the entries in column $j$ of this array. Each column has at least as many entries as the column to its right, and every entry greater than $1$ is exactly twice the entry to its right in the same row, so $b_j\ge2b_{j+1}$ : the resulting sequence is type $B$ . Since both $a_1+\cdots+a_k$ and $b_1+\cdots+b_m$ equal the total sum of all array entries, the sequence $(b_j)$ also sums to $n$ .