IMO 1997 SL 24

Origin: LIT

Problem

For a positive integer n, let f(n) denote the number of ways to represent n as the sum of powers of 2 with nonnegative integer exponents. Representations that differ only in the ordering in their summands are not considered to be distinct. (For instance, f(4) = 4 because the number 4 can be represented in the following four ways: 4; 2+2; 2+1+1; 1+1+1+1.) Prove that the inequality 2n2/4 < f(2n) < 2n2/2 holds for any integer n \geq3.

Solution

There is a bijective correspondence between representations in the given form of 2k and 2k + 1 for k = 0, 1, . . ., since adding 1 to every represen- tation of 2k, we obtain a representation of 2k + 1, and conversely, every representation of 2k + 1 contains at least one 1, which can be removed. Hence, f(2k + 1) = f(2k). Consider all representations of 2k. The number of those that contain at least one 1 equals f(2k −1) = f(2k −2), while the number of those not containing a 1 equals f(k) (the correspondence is given by division of summands by 2). Therefore f(2k) = f(2k −2) + f(k). (1) Summing these equalities over k = 1, . . . , n, we obtain f(2n) = f(0) + f(1) + \cdot \cdot \cdot + f(n). (2) We first prove the right-hand inequality. Since f is increasing, and f(0) + f(1) = f(2), (2) yields f(2n) \leqnf(n) for n \geq2. Now f(23) = f(0) + \cdot \cdot \cdot + f(4) = 10 < 232/2, and one can easily conclude by induction that f(2n+1) \leq2nf(2n) < 2n \cdot 2n2/2 < 2(n+1)2/2 for each n \geq3. We now derive the lower estimate. It follows from (1) that f(x+2)−f(x) is increasing. Consequently, for each m and k < m we have f(2m + 2k) − f(2m) \geqf(2m + 2k −2) −f(2m −2) \geq\cdot \cdot \cdot \geqf(2m) −f(2m −2k), so f(2m + 2k) + f(2m −2k) \geq2f(2m). Adding all these inequalities for k = 1, 2, . . ., m, we obtain f(0) + f(2) + \cdot \cdot \cdot + f(4m) \geq(2m + 1)f(2m). But since f(2) = f(3), f(4) = f(5) etc., we also have f(1) + f(3) + \cdot \cdot \cdot + f(4m −1) > (2m −1)f(2m), which together with the above inequality gives f(8m) = f(0) + f(1) + \cdot \cdot \cdot + f(4m) > 4mf(2m). (3) Finally, we have that the inequality f(2n) > 2n2/4 holds for n = 2 and n = 3, while for larger n we have by induction f(2n) > 2n−1f(2n−2) > 2n−1+(n−2)2/4 = 2n2/4. This completes the proof. Remark. Despite the fact that the lower estimate is more difficult, it is much weaker than the upper estimate. It can be shown that f(2n) eventually (for large n) exceeds 2cn2 for any c < 1 2.