Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If $x \geq 2$, then how do we prove that $$\int_{2}^{x} \frac{\mathrm dt}{\log^{n}{t}} = O\Bigl(\frac{x}{\log^{n}{x}}\Bigr)?$$

share|improve this question
add comment

5 Answers

up vote 15 down vote accepted

Here is a way to prove it without knowing the answer before hand.

Let $c > 2$ be a number such that $c > e^{n+1}$.

It is enough to consider

$$\int_{c}^{x} \frac{dt}{\log^n t}$$

Integrating by parts, we get

$$\int_{c}^{x} \frac{dt}{\log^n t} = \frac{x}{\log^n x} - K + n \int_{c}^{x} \frac{dt}{\log^{n+1} t}$$

Now $$n\int_{c}^{x} \frac{dt}{\log^{n+1} t} \le \frac{n}{n+1} \int_{c}^{x} \frac{dt}{\log^n t} $$

as $\log t \ge n+1$ for $t \ge c$

Thus $$\frac{1}{n+1}\int_{c}^{x} \frac{dt}{\log^n t} < \frac{x}{\log^n x} $$

In fact, we have that

$$\int_{2}^{x} \frac{dt}{\log^n t} = \theta(\frac{x}{\log^n x})$$

share|improve this answer
    
I fail to see how this is substantially different from what I wrote. Perhaps some consider integration by parts different from the Leibniz rule? =) –  Willie Wong Oct 25 '10 at 15:54
1  
@Willie: The point is that we can start just from the integral without having even the slightest clue about it being $O(x/\log^n x)$. FWIW, I already upvoted your answer, but the fact that we knew the answer and were using that fact bothered me. So I tried to post one where we didn't know the answer beforehand. –  Aryabhata Oct 25 '10 at 16:04
    
I understand that part, but like I said: integration by parts and Leibniz rule are two sides of the same coin. And some point you will have to make use of the same observation. I mean, if you really want to "write the way you come up with the answer", you couldn't have chosen $c > e^{n+1}$ as a first step: you would've had to assign the value of $c$ in the second to the last step. –  Willie Wong Oct 25 '10 at 16:35
    
It's not like I want you to remove your post or anything (see my smiley at the end of my first comment). I personally feel that this "knowing the answer" business is false dichotomy. I feel a one-line formula is more aesthetically pleasing; even had I not known the answer before hand I would've written the proof the same way. You, on the other hand, think 5 lines of integrals is more clear. The whole point of my original comment was that mathematically our two answers are the same, despite the different presentation. And now you're making me make a mountain out of a molehill. =) –  Willie Wong Oct 25 '10 at 16:39
    
@Willie: No one is disputing that product rule of derivatives and integration by parts are sides to same coin. I don't understand your issue with c. This is done all the time. You work out some variables you need as you work through, and when you find some values that work, you just present them before hand, to make for a cleaner proof. As to your later comment, I am not making mountains out of anything :-). I just let you know the motivation for posting my answer. –  Aryabhata Oct 25 '10 at 16:41
show 5 more comments

Consider

$$ \frac{d}{dx} \frac{x}{\log^n(x)} = \frac{1}{\log^n(x)} - \frac{n}{\log^{n+1}(x)} = \frac{1}{\log^n(x)}\left( 1 - \frac{n}{\log x}\right)$$

For sufficiently large $x$, the RHS is bigger than $\frac12 \frac{1}{\log^n(x)}$, and hence we get the asymptotic bound we need. The usual arguments then gives you a sufficiently large constant for the Big O.

share|improve this answer
    
Just for the fun of dropping oil on a dead fire : I like this proof better, more clean. =) Haha! –  Patrick Da Silva Jun 15 '11 at 6:01
add comment

Here is yet another approach:

Let $2\leq f(x)\leq x$ be some function which we will soon chose depending on $x$. Then splitting the integral we have $$\int_{2}^{x}\frac{1}{\log^{n}t}dt\leq\int_{2}^{f(x)}\frac{1}{\log^{n}t}dt+\int_{f(x)}^{x}\frac{1}{\log^{n}t}dt\leq f(x)+\frac{x}{\log^{n}\left(f(x)\right)}.$$ Hence, taking $f(x)=\frac{x}{\log^{n+1}x}$ (or even $f(x)=xe^{-c\sqrt{\log x}}$ ) we conclude $$\int_{2}^{x}\frac{1}{\log^{n}t}dt\ll\frac{x}{\log^{n+1}x}. $$

share|improve this answer
add comment

Another way of dealing with this integral is to let $t = e^u$, so you are trying to bound $$\int_{\ln 2}^{\ln x}{e^u \over u^n}\,du$$ Clearly it suffices to replace $\ln 2$ with any fixed constant $c$ since the difference is a constant that doesn't affect asymptotics. Integrating by parts gives $$\int_c^{\ln x}{e^u \over u^n}\,du = {x \over (\ln{x})^n} - {e^c \over c^n}+\int_c^{\ln x}{ne^u \over u^{n+1}}\,du$$ If $c$ is large enough the integrand on the right is less than half that on the left, so the integral is less than half of the left integral. Subtracting gives $$\int_c^{\ln x}{e^u \over u^n}\,du = {2x \over (\ln{x})^n} - {2e^c \over c^n}$$ $$< {2x \over (\ln{x})^n}$$

share|improve this answer
add comment

Put $$ f(x)=\int_2^x {\frac{{dt}}{{\log ^n t}}} \;\; {\rm and} \;\; g(x)=\frac{x}{{\log ^n x}}. $$ Then, $$ f'(x)=\frac{1}{{\log ^n x}} \;\; {\rm and} \;\; g'(x)=\frac{{\log ^n x - n\log ^{n - 1} x}}{{\log ^{2n} x}}. $$ Hence $$ \mathop {\lim }\limits_{x \to \infty } \frac{{f(x)}}{{g(x)}} = \mathop {\lim }\limits_{x \to \infty } \frac{{f'(x)}}{{g'(x)}} = \mathop {\lim }\limits_{x \to \infty } \frac{{\log ^n x}}{{\log ^n x - n\log ^{n - 1} x}} = \mathop {\lim }\limits_{x \to \infty } \frac{1}{{1 - n/\log x}} = 1. $$ That is, $f$ is asymptotically equal to $g$ as $x \to \infty$ (written as $f \sim g$); in particular, $f = O(g)$ as $x \to \infty$.

EDIT: The asymptotic equivalence $$ \int_2^x {\frac{{dt}}{{\log ^n t}}} \sim \frac{x}{{\log ^n x}} \;\; {\rm as} \; x \to \infty, $$ derived elementarily above (and which is much more than the OP asked for), also follows as a very special case from the theory of Regular variation. The function $L(x)=1/(\log ^n x)$, $x \geq 2$, is slowly varying (at infinity), for any $n \in \mathbb{R}$, and is bounded on every compact subset of $[2,\infty)$. Thus, by Karamata's integral theorem (Theorem A.9 here),

(a) for $\alpha > -1$, $$ \int_2^x {t^\alpha L(t)dt} \sim \frac{{x^{\alpha + 1} }}{{\alpha + 1}}L(x) \;\; {\rm as} \; x \to \infty; $$

(b) for $\alpha < -1$, $$ \int_2^x {t^\alpha L(t)dt} \sim - \frac{{x^{\alpha + 1} }}{{\alpha + 1}}L(x) \;\; {\rm as} \; x \to \infty. $$

In particular (letting $\alpha = 0$ in (a)), $$ \int_2^x {L(t)dt} \sim xL(x) \;\; {\rm as} \; x \to \infty, $$ that is, $$ \int_2^x {\frac{{dt}}{{\log ^n t}}} \sim \frac{x}{{\log ^n x}} \;\; {\rm as} \; x \to \infty. $$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.