Let be a positive integer. Prove that can be expressed as a sum of distinct powers of .
Solution
First, we observe that for every positive integer (it can be proved easily by induction).
Consider a positive integer (for we have ). Let be the number of ones in the binary representation of . Then,
where the exponents are all distinct and smaller than , due to our initial remark. We express as follows:
and, since , we obtain:
Note that is a sum of distinct powers of whose exponents are all greater than or equal to . After cancelation of terms (recall that are smaller than ), it turns out that is a sum of distinct powers of whose exponents are all smaller than . Therefore, the expression obtained is a sum of distinct powers of .
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.