# Finding the summation of the floor of the series identity

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)$

$$\sum_{i=1}^n\left\lfloor\frac{n}i\right\rfloor=\sum_{k=1}^nd(k)$$

-

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.

-
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.

-
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