Question: Does $\displaystyle \sum_{i=1}^n f(i)\sim n \log n$ and $f$ monotonous increases means $f(n)\sim \log n$, where $f$ is always positive? $A(n)\sim B(n)$ means: $$ \lim_{n\to\infty } A(n)/B(n)=1 $$
I haven't got any ideas yet(in fact, I don't even know where to begin my solution). Can anyone helps me?
Let $S_n=\sum_{i=1}f(i)$. Because $f$ is increasing we note that $$nf(n)\le \sum_{i=n+1}^{2n}f(i)=S_{2n}-S_n$$ So $$\frac{f(n)}{\log n}\le 2\frac{\log n+\log2}{\log n}\cdot\frac{S_{2n}}{2n\log(2n)}-\frac{S_n}{n\log n}$$ It follows that $$\limsup_{n\to\infty}\frac{f(n)}{\log n}\le 2-1=1.\tag{1}$$ Similarly, $$nf(2n)\ge \sum_{i=n+1}^{2n}f(i)=S_{2n}-S_n$$ So $$\frac{f(2n)}{\log2n}\ge 2\frac{S_{2n}}{2n\log(2n)}-\frac{S_n}{n(\log n+\log2)}$$ It follows that $$\liminf_{n\to\infty}\frac{f(2n)}{\log2n}\ge 2-1=1.\tag{2}$$ Combining (1) and (2) we see that $$\lim_{n\to\infty}\frac{f(2n)}{\log2n}=1.\tag{3}$$ Now $$\frac{\log2n}{\log(2n+1)}\cdot\frac{f(2n)}{\log2n}\le \frac{f(2n+1)}{\log(2n+1)}\le \frac{\log2n}{\log(2n+1)}\cdot\frac{f(2n+2)}{\log(2n+2)}$$ Taking limits we conclude that $$\lim_{n\to\infty}\frac{f(2n+1)}{\log(2n+1)}=1.\tag{4}$$ From (3) and (4) the result follows.