Number Theory Inequality Proof

For positive integer $n>0 \in \mathbb{N}$, prove that $\sigma (1) + \sigma (2) + \cdots + \sigma (n) \leq n^2$.

I tried listing out the first few terms, but it doesn't really help that much. I also tried to simplify each term by splitting it up into prime factors( Note: This is not for all terms) but that didn't yield anything useful.

Solution 1:

You have $$\sum_{k=1}^n\sum_{d|k} d$$ Rearrange it to $$\sum_{d=1}^n\sum_{m=1}^{n/d} d$$

Solution 2:

Note that $\sigma(n)$ is the sum of the divisors of $n$. It follows that, for $d≤n$, $d$ appears once in the sum for every integer less than $n$ divisible by $d$. Thus your sum is equal to $$\sum_{d=1}^n \Big\lfloor \frac nd\Big \rfloor d<n\sum_{d=1}^n \frac 1d\times d=n\times n=n^2$$