Tuesday, August 23, 2016

calculus - How big is $displaystyle int_{1}^x sqrt t left( sqrt{frac{log (t+1)}{log(t)}}+ sqrt{frac{log (t)}{log(t+1)}}-2,right) dt$?



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?


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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...