Maths Olympiad Prep

Library / /4 of 24

Algebra Difficulty 5.2 AIME, harder Prove it Argentina

Let nn be a positive integer. Prove that n(2n1)n(2^n - 1) can be expressed as a sum of nn distinct powers of 22.

Solution

First, we observe that n<2nn < 2^n for every positive integer nn (it can be proved easily by induction).
Consider a positive integer n2n \ge 2 (for n=1n = 1 we have 1(211)=201 \cdot (2^1 - 1) = 2^0). Let kk be the number of ones in the binary representation of n1n-1. Then,
n1=2m1++2mk, n-1 = 2^{m_1} + \dots + 2^{m_k},
where the exponents m1,,mkm_1, \dots, m_k are all distinct and smaller than nn, due to our initial remark. We express n(2n1)n(2^n - 1) as follows:
n(2n1)=(n1)2n+[(2n1)(n1)], n(2^n - 1) = (n-1)2^n + [(2^n - 1) - (n-1)],
and, since 2n1=2n1+2n2++21+202^n - 1 = 2^{n-1} + 2^{n-2} + \dots + 2^1 + 2^0, we obtain:
n(2n1)=(2m1++2mk)2n+[(2n1++21+20)(2m1++2mk)]==2n+m1++2n+mkA+[(2n1+2n2++21+20)(2m1++2mk)]B. n(2^n - 1) = (2^{m_1} + \dots + 2^{m_k})2^n + [(2^{n-1} + \dots + 2^1 + 2^0) - (2^{m_1} + \dots + 2^{m_k})] = \\ = \underbrace{2^{n+m_1} + \dots + 2^{n+m_k}}_{A} + \underbrace{[(2^{n-1} + 2^{n-2} + \dots + 2^1 + 2^0) - (2^{m_1} + \dots + 2^{m_k})]}_{B}.
Note that AA is a sum of kk distinct powers of 22 whose exponents are all greater than or equal to nn. After cancelation of terms (recall that m1,,mkm_1, \dots, m_k are smaller than nn), it turns out that BB is a sum of nkn-k distinct powers of 22 whose exponents are all smaller than nn. Therefore, the expression obtained is a sum of k+(nk)=nk + (n-k) = n distinct powers of 22.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.