Show $\sum_{n = 1}^N \frac{\log(n) + 1}{n + 1} = O\left(\log(N)^2\right)$

Question

I am not good with inequalities or big-O notation. Here is my attempt:

It suffices to show that $\sum_{n = 1}^N \frac{\log(n) + 1}{n + 1} \leq \log(N)^2$. We have

\begin{align*} \sum_{n = 1}^N \frac{\log(n) + 1}{n + 1} &\leq \sum_{n = 1}^N \frac{\log(n) + 1}{n}\\ &= \sum_{n = 1}^N \frac{\log(n)}{n} + \sum_{n = 1}^N \frac{1}{n}\\ &\leq \sum_{n = 1}^N \frac{\log(n)}{n} + 1 + \log(N) \end{align*}

I'm not sure if I'm making the right moves, but at any rate I'm stuck. Thanks.

Answer 1

Just for your curiosity.

Since the integral is simple $$\int \frac{\log (n)+1}{n+1}\,dn=\text{Li}_2(-n)+(\log (n)+1) \log (n+1)$$ the simplest form of Euler-MacLaurin summation gives $$\sum_{n=1}^N \frac{\log (n)+1}{n+1}=C+\log (N)+\frac{1}{2}\log ^2(N)+\frac{3 \log (N)+5}{2 N}+O\left(\frac{\log (N)}{N^2}\right)$$

For this level of summation $$C=\frac{4487221}{19353600}-\frac{\pi ^2}{12}-\log (2)$$

For $n=1000$, this gives $29.49540$ while the exact summation gives $29.49502$.

The relative error is smaller than $1$% when $n \geq 10$, smaller than $0.1$% when $n \geq 20$, smaller than $0.01$% when $n \geq 81$.

Answer 2

The function $x \mapsto \frac{\log(x)+1}{x}$ is decreasing for $x \ge 1$, therefore the sum can be estimated above by an integral: $$ \sum_{n = 1}^N \frac{\log(n) + 1}{n + 1} \leq \sum_{n = 1}^N \frac{\log(n) + 1}{n} \le 1 + \int_1^N \frac{\log(x)+1}{x} \, dx \\ = 1 + \log(N) + \frac 12 \log(N)^2 = O\left( \log(N)^2\right) \, . $$