Problem

Source: APMO 2017, problem 3

Tags: combinatorics, APMO



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,\cdots{},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\ge 2b_{j+1}$ holds $(j=1,2,\cdots{}, m-1)$. Prove that $A(n) = B(n)$ for every positive integer $n$. Senior Problems Committee of the Australian Mathematical Olympiad Committee