Is this number in $O(\log(n))$?

Question

Is this number $\big[\log(n) + \sum_{j=1}^{n-1} (\log(j) - (j+1)(\log(j+1)) + j \log(j) +1)\big] \in O(\log(n))$?

I simplified it to $\big[\log(n) + \sum_{j=1}^n (-\log(n+1) - j(\log(n)) + 1)\big]$.

Answer 1

\begin{align*}\sum_{j=1}^{n-1} (\log(j) - (j+1)(\log(j+1)) + j \log(j) +1) &= \\ \sum_{j=1}^{n-1} ( - (j+1)(\log(j+1)) + (j+1) \log(j) +1) &= \\ \sum_{j=1}^{n-1} ( (j+1)(\log(j)-\log(j+1)) +1) \end{align*}

So I don't think your simplification is correct.

Now use $\ln(n) = H_n + \gamma + \frac1{2n}+O\left(\frac1{n^2}\right)$. This gives $$\ln(n)-\ln(n+1) = H_n - H_{n+1} - \frac1{2n+2} -\frac1{2n}+O\left(\frac1{n^2}\right) = \frac{-1}{n+1}+O\left(\frac1{n^2}\right)$$

Thus $$(n+1)(\ln(n)-\ln(n+1)) = -1 +O\left(\frac1n\right)$$

$$(n+1)(\ln(n)-\ln(n+1))+1 = O\left(\frac1n\right)$$

$$\sum_{j=1}^{n-1} ( (j+1)(\log(j)-\log(j+1)) +1) = O\left(\ln(n)\right)$$

$$\sum_{j=1}^{n-1} ( (j+1)(\log(j)-\log(j+1)) +1) = O\left(\log(n)\right)$$

$$\log(n) + \sum_{j=1}^{n-1} ( (j+1)(\log(j)-\log(j+1)) +1) = O\left(\log(n)\right)$$