showing that the partial sums of $ \log(j) = n\log(n) - n + \text{O}(\log(n))$

Question

I'm trying to show that the partial sums of $\log(j) = n\log(n) - n + \text{O}(\log(n))$

I know that $$\int_1^n\log(x)dx = n\log(n) - n + 1$$

so that this number is pretty close to what I want.

Now I look at the difference between sum and integral of log:

$$\sum_{j=1}^n \log(j) - \int_1^n \log(x)dx$$

My work:

Working out the arithmetic and simplifying as much as possible, I am now at $$\sum_{j=1}^n \log(j) - \int_1^n \log(x)dx = \log(n) + \sum_{j=1}^{n-1} \big[\log(\large \frac{1}{1+\frac{1}{j}}) - \log(1 + \frac{1}{j})(j) + 1]$$

Where can I go from here? I think I would want to show that this difference, i.e. the R.H.S., is actually $O(\log(n))$ ...

Thanks,

Answer 1

It is a direct application of Abel's summation. We have $$\sum_{k\leq n}\log\left(k\right)=\sum_{k\leq n}1\cdot\log\left(k\right)=n\log\left(n\right)-\int_{1}^{n}\frac{\left\lfloor t\right\rfloor }{t}dt $$ where $\left\lfloor t\right\rfloor $ is the floor function and using $\left\lfloor t\right\rfloor =t+O\left(1\right) $ we have $$\sum_{k\leq n}\log\left(k\right)=n\log\left(n\right)-n+1+O\left(\int_{1}^{n}\frac{1}{t}dt\right)=n\log\left(n\right)-n+O\left(\log\left(n\right)\right).$$

Answer 2

You have $\log(1+1/j) = 1/j+O(1/j^2)$, so $\sum_{j=2}^n \frac1{\log(1+1/j)} \approx \sum_{j=2}^n (-1/j+O(1/j^2)) \approx -\log(n)+O(1) $ and (I think you mean $n$ in this expression instead of $j$) $n\log(1+1/n) \approx 1$ , which, I think, gives you what you want.