Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I would appreciate if somebody could help me with the following problem:

Q: How to proof ?

The number of positive divisors of $n$ is denoted by $d(n)$


share|cite|improve this question
up vote 4 down vote accepted

This is basically just interchanging the order of the sums.

$$\sum_{k=1}^n d(k) = \sum_{k\le n} \sum_{d\mid k} 1 = \sum_{\substack{k\le n\\d\mid k}} 1 = \sum_{qd\le n} 1 = \sum_{d\le n} \sum_{q\le \frac nd} 1 =\sum_{d\le n} \left\lfloor \frac nd \right\rfloor= \sum_{d=1}^n \left\lfloor \frac nd \right\rfloor$$

All summations are only taken through integer indices.

I leave to you to check in detail whether $\{(k,d); k,d\in\mathbb N, k\le n, d\mid k, \}=\{(qd,d); q,d\in\mathbb N, qd\le n\}=\{(dq,d); q,d\in\mathbb N, q\le\frac nd\}$, which is the reason why there are only different expressions of the same sum.

share|cite|improve this answer
Maybe I could also mention that you will see arguments of this type quite frequently if you read Apostol's Introduction to Analytic Number Theory. (And probably in many other books from that area.) – Martin Sleziak Mar 22 '14 at 11:32

Proof by induction. If $n=1$, $1=d(1)$ True.

Assume for $n=q$,

Then $$\sum_{i=1}^q\left\lfloor\frac{q}i\right\rfloor=\sum_{k=1}^qd(k)$$

Add $d(q+1)$ to both sides we have $$\lfloor\frac{q}{1} \rfloor+ \lfloor\frac{q}{2} \rfloor + \cdots + \lfloor\frac{q}{q} \rfloor + d(q+1)=\sum_{k=1}^{q+1}d(k)$$

But the number of divisors of $q+1$ -1 is the number of times the floor functions increase by 1. Therefore by induction it holds.

share|cite|improve this answer
If I understand you correctly, by the last line of your post you mean that $\left\lfloor\frac{q+1}k\right\rfloor-\left\lfloor\frac{q}k\right\rfloor=1$ if and only if $k\mid q+1$. (And it is zero in all remaining cases.) – Martin Sleziak Mar 22 '14 at 10:41
Yes, i do thanks. – John Marty Mar 23 '14 at 0:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.