How $\sum_{i=2}^{\sqrt n}\log_{i}(n)$ increases

Question

I need to know in which way this sum increases:

$\sum_{i=2}^{\sqrt n}\log_{i}(n)$

I believe it increases like $\sqrt n$ but I don't know how to demonstrate it.

Answer 1

Our sum is $\ln n\cdot\sum_{i=2}^{\sqrt{n}}\frac{1}{\ln i}$. There's an obvious integral approximation,$$\ln n\cdot\int_2^{\sqrt{n}}\frac{dx}{\ln x}=\operatorname{Li}(\sqrt{n})\ln n.$$From a famous result, this is $O(\sqrt{n})$, as you expected.

Answer 2

We have

$$\sum_{k=2}^{\sqrt n}\log_k(n)=\ln(n)\sum_{k=2}^{\sqrt n}\frac1{\ln(k)}\sim\ln(n)\frac{\sqrt n}{\ln(\sqrt n)}=2\sqrt n$$

from a simple application of summation by parts.