Question

4. The goal of this problem is to prove the inequality in part (b), that o(1)+(2)+...+on) < nº for each positive integer n. The first part is a stepping-stone for that. (a) (10 points.) Fix positive integers n and k with 1 <ksn. (i) For which integers i with 1 <i<n is k a term in the sum that defines oo)? (ii) How many such integers i are there? (The answer depends on n and k. Another way to phrase question (ii) is this: how many times does k occur in the sum o(1) + (2) + ... +on) if you write each o(i) as a sum?) Explain your answer. (b) (10 points. Use the result in part (a) to prove that o(1) + (2)+...+on) < n2 for each positive integer n.

DEFINITION: For a positive integer n, τ(n) is the number of positive divisors of n and σ(n) is the sum of those divisors.

Answer 1

Solution :
4.
(a)
(i)
For any positive integer i,
$\sigma$ (i) is the sum of all positive divisors of i.

If k occurs as a term in the sum defining $\sigma$ (i), then k has to be a positive divisor of i, or equivalently, i is a positive multiple of k.
Hence, the set of positive integers i between 1 and n for which k occurs as a term in the sum defining $\sigma$ (i) is
{ kt : 1 $\leq$ kt $\leq$ n , t is a positive integer }.

(ii)
The total number of such integers i is the total number of multiples of k between 1 and n.

Suppose that the multiples of k between 1 and n are k,2k,3k, .... , tk where t is the greatest integer such that tk $\leq$ n.
Equivalently, t is the greatest integer such that t $\leq$ n/k. Thus, t = [n/k] where [.] is the greatest integer function.
Thus, the total number of multiples of k between 1 and n is t = [n/k].
Hence, the total number of such integers i is [n/k].

(b)
Now, observe that for any 1 $\leq$ i $\leq$ n, since $\sigma$ (i) is the sum of all positive divisors of i, hence if every $\sigma$ (i) is written as a sum, then every term in $\sigma$ (1)+$\sigma$(2)+$\sigma$(3)+....+$\sigma$(n) is a positive integer between 1 and n (because every such term is a divisor of one of the integers 1,2,3,....n).

Now, by part (a), it follows that if 1 $\leq$ k $\leq$ n, then the number of times k occurs in the sum $\sigma$ (1)+$\sigma$(2)+...+$\sigma$(n) is [n/k].
Further, as seen in the last paragraph, there are no terms in the sum $\sigma$ (1)+$\sigma$(2)+...+$\sigma$(n) which are strictly greater than n.

Hence,
$\sigma(1)+\sigma(2)+...+\sigma(n) = \sum_{1\leq k \leq n} k.[n/k] \leq \sum_{1\leq k \leq n} k. n/k = \sum_{1\leq k \leq n} n = n^2$  

where the inequality follows since for any real number x, [x] $\leq$ x by definition of the Greatest Integer Function.

This proves the result.