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:
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?
Answer
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.
No comments:
Post a Comment