Finding the summation of the floor of the series identity

Question

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

Answer 1

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.

Answer 2

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.