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 1 of 4: Expand a type-

A

sequence into a left-aligned array

Previous step Next step

a_i=2^{N_i-1}+2^{N_i-2}+\cdots+2^1+2^0

Detailed analysis

Call a sequence of type $A$ if each term satisfies $a_i+1=2^{N_i}$ for some positive integer $N_i$ , and of type $B$ if $b_j\ge2b_{j+1}$ for consecutive terms. Given a type- $A$ sequence $a_1\ge\cdots\ge a_k$ , expand each $a_i=2^{N_i-1}+\cdots+2^1+2^0$ using the identity $2^{N}-1=2^{N-1}+\cdots+2+1$ , and write these powers of two as a left-aligned array with row $i$ holding the expansion of $a_i$ ; the rows have non-increasing length since $a_1\ge\cdots\ge a_k$ .