Track / Stage 4 / 235 of 340 #1135 of 2604

Problem 1135

AMC 12 late, AIME early

Number theory Difficulty 4.8 Prove it Harvard-MIT Mathematics Tournament · United States

Let $\sigma(n)$ denote the sum of the (positive) divisors of $n$ , including $1$ and $n$ itself.
Prove that
$\sigma(1)+\sigma(2)+\sigma(3)+\cdots+\sigma(n) \leq n^{2}$
for every positive integer $n$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution:
The $i$ th term on the left is the sum of all $d$ dividing $i$ . If we write this sum out explicitly, then each term $d=1,2,\ldots,n$ appears $\lfloor n/d \rfloor$ times—once for each multiple of $d$ that is $\leq n$ . Thus, the sum equals
$\begin{aligned} \lfloor n/1 \rfloor + 2\lfloor n/2 \rfloor + 3\lfloor n/3 \rfloor + \cdots + n\lfloor n/n \rfloor &\leq n/1 + 2n/2 + 3n/3 + \cdots + n/n \\ &= n + n + \cdots + n \\ &= n^{2}. \end{aligned}$

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.