Proof explanation of $\sum_{i=1}^{n} \lfloor\log\left(\frac{n}{i}\right)\rfloor$

Question

$(1)$ The first relation. $$ \left\lfloor \log_2\frac{n}{i} \right\rfloor=j \Longleftrightarrow 2^j \leq \frac{n}{i} < 2^{j+1} \Longleftrightarrow \frac{n}{2^{j+1}} < i \leq \frac{n}{2^j} \space\space $$

Therefore, $(2)$ The second relation as follows $$ \sum_{i=1}^n\left\lfloor \log_2\frac{n}{i} \right\rfloor\leq \sum_{j=1}^{\lfloor \log_2n \rfloor}j\cdot\left(\frac{n}{2^{j+1}}+1\right)=O(\log^2n)+n \cdot \sum_{j=1}^{\infty}{\frac{j}{2^{j+1}}}=O(\log^2n)+n $$

I don't know how can we get $(2)$ from $(1)$; Moreover, why and how can we simplify $(2)$ like that.

Answer 1

By $(1)$, the number of integers $i$ such that $\left\lfloor \log_2\frac{n}{i} \right\rfloor=j$ is $$\left\lfloor \frac n{2^j}\right\rfloor-\left\lceil\frac n{2^{j+1}}\right\rceil+1\le\frac n{2^j}-\frac n{2^{j+1}}+1=\frac n{2^{j+1}}+1,$$ whence the $\le$ in $(2).$

For the next $=,$ use that $$\sum_{j=1}^{\lfloor \log_2n \rfloor}j=\frac{\lfloor \log_2n \rfloor(\lfloor \log_2n \rfloor+1)}2\le \frac{(\log_2n)(\log_2n+1)}2=O(\log_2^2n).$$

Finally, $$\sum_{j=1}^{\infty}{\frac{j}{2^{j+1}}}=1.$$