During the analysis of an optimization algorithm I encountered the following sum

$\displaystyle \sum_{n=1}^N\sqrt n \left( \sqrt{\frac{\log (n+1)}{\log(n)}}+ \sqrt{\frac{\log (n)}{\log(n+1)}}-2\,\right)$

I am interested in the order of the above as $N \to \infty$.

For the moment let's assume the terms are decreasing as this allows us estimate the sum using the corresponding integral, which tends to be easier to work with since we can do substitutions and other tricks.

The integral seems to grow incredibly slowly. For example see https://www.desmos.com/calculator/y5fs86fbzw where the integrand is orange and the integral is green:

enter image description here

The integral is about $0.7$ for $x=10$ and $0.712$ for $x$ equal one million. It is very quickly outpaced by $\log(\log x)$ and if you click the link and scroll to the right you'll see it's eventually outpaced by $\log(\log (\log x))$.

I would wager the integral tends to infinity but is eventually outpaced by any $\log^n(x)$.

If you estimate $\log(x+1) \simeq \log(x)+1/x$ for large $x$ and $\sqrt {1+\epsilon} \simeq 1 + \frac{\epsilon}{2}$ for small $\epsilon$ you see the square roots are approximately $\displaystyle 1 \pm \frac{1}{2 x \log (x)} $ but with opposite signs. Hence they cancel the $2$ and you end up with $\sqrt x$ times their difference. That should be very small indeed.

Any ideas on how to proceed?

  • 1
    $\begingroup$ The summand is asymptotic to$$\frac{1}{4n^{3/2}\log^2{(n)}}+o\left(\frac1{n^{5/2}}\right)$$as $n\to\infty$. $\endgroup$ – Peter Foreman Oct 14 '19 at 17:22
  • $\begingroup$ The series converges assuming you omit the term $n=1$ which causes the summand to be undefined due to $\log{(1+1)}/\log{(1)}=\log{(2)}/0$ $\endgroup$ – Peter Foreman Oct 14 '19 at 17:30

As Peter Foreman hinted in their comment: one can use power series to get more precise approximations than $\sqrt{1+\varepsilon} \approx 1+\varepsilon/2$, for example $\sqrt{1+\varepsilon} =1+\varepsilon/2 - \varepsilon^2/8 + O(\varepsilon^3)$.

In this way one can show that \begin{align*} \sqrt{\frac{\log(t+1)}{\log t}} &= 1+\frac{1}{2 t \log t}+\frac{-2 \log t-1}{8 t^2 \log^2t}+O\big(t^{-3}\big) \\ \sqrt{\frac{\log t}{\log(t+1)}} &= 1-\frac{1}{2 t \log t}+\frac{2 \log t+3}{8 t^2 \log^2t}+O\big(t^{-3}\big), \end{align*} which shows that your integral is $$ \int_1^x \bigg( \frac1{4t^{3/2}(\log t)^2} + O\big(t^{-5/2}\big) \bigg)\,dt, $$ and in particular does not tend to infinity but in fact is convergent.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.