Let be a positive integer. Prove that every integer between and can be written as the sum of at most distinct positive divisors of .
Romanian Mathematical Olympiad
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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.