The ith summand on the left-hand side is the sum of all the divisors
of i . If we write out all these summands on the left-hand side explicitly,
each number d, with 1 ≤ d ≤ n, appears
! n
d
"
times, once for each multiple
of d that is less than or equal to n. Hence the left-hand side of the desired
inequality is equal to