Let be a positive integer. Prove that every integer between and can be written as the sum of at most distinct positive divisors of .
Solution
We use induction on ; the base case is obvious.
Suppose now that the conclusion holds for some positive integer and consider . Then , , . It is easily noticed that , therefore can be written as a sum of (at most) divisors of – denote them , , whence
and are divisors of .
If , the induction step is finished. Otherwise , divides and , therefore can be written as the sum of distinct divisors of , with and we are done.
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.