Problem

Source: APMO 2017, problem 3

Tags: combinatorics, APMO



Let A(n) denote the number of sequences a1a2ak of positive integers for which a1++ak=n and each ai+1 is a power of two (i=1,2,,k). Let B(n) denote the number of sequences b1b2bm of positive integers for which b1++bm=n and each inequality bj2bj+1 holds (j=1,2,,m1). Prove that A(n)=B(n) for every positive integer n. Senior Problems Committee of the Australian Mathematical Olympiad Committee