# Showing that $\frac{1}{n}\sum\limits_{j = 1}^{n} \left\lfloor \frac{n}{j} \right\rfloor \approx \log(n)$ (with error bounded by 1) using Riemann Sum

Here is my solution so far, but it just doesn't seem right:

Define a function $$\sigma_0(x) = \sum\limits_{d \mid x} 1$$ on the interval $$[1, N]$$. The partitions for the Riemann Sum will be of equal length 1 from $$[1, N]$$. Further, let $$x_j = j$$ for $$j = 1, 2, \ldots, N$$. Define $$R_N = \sum\limits_{j = 1}^{N} \sum\limits_{d \mid j} \left( \frac{N}{j} - \left\lfloor\frac{N}{j}\right\rfloor\right)$$ Now, we can use Riemann Sums to estimate that $$\sum\limits_{j = 1}^{N} \sum\limits_{d \mid j} 1\approx \int_{1}^{N} \left[\sum\limits_{d \mid x} 1\right]dx = \sum\limits_{j = 1}^{N} \left\lfloor \frac{N}{j} \right\rfloor$$ Further, since $$R_N$$ is always greater than 0 but strictly less than $$N$$, we have that $$A(N) = \frac{1}{N} \sum\limits_{j = 1}^{N} \sum\limits_{d \mid j} 1 \approx \frac{1}{N} \sum\limits_{j = 1}^{N} \left\lfloor \frac{N}{j} \right\rfloor \approx \frac{1}{N} \log(N) + C$$ Recall that the error between the actual value of an integral and its approximation by a finite sum of rectangles is bounded by the width of the rectangles multiplied by the maximum value of the integrand. In our case, $$\left\lfloor\frac{N}{j}\right\rfloor$$ is the maximum value of the integrand and $$\frac{1}{N}$$ is the width of each rectangle. Thus, the error is at most $$\frac{1}{N} \left\lfloor\frac{N}{j}\right\rfloor$$ which is equal to 1 when $$j = 1$$. Therefore the error is bounded by 1.

Just observe that: $$\left\lfloor \frac{n}{j} \right\rfloor\leq \frac{n}{j}$$. So, $$\frac{1}{n} \sum_{j=1}^{n} \left\lfloor \frac{n}{j} \right\rfloor < \frac{1}{n} \sum_{j=1}^{n} \frac{n}{j} = \sum_{j=1}^{n} \frac{1}{j} < \log(n) +1.$$ You can find the approximation of the harmonic sum here.