Proving $(\log x)^a = O( x^b ) $ for any positive a,b

Question

I am told that showing this is the same as showing that

$$ \lim_{x \to \infty} \frac{ x^b }{ (\log x )^a } = \infty.$$

I can solve this limit easily by the rule of L'Hospital:

$$ \lim_{x \to \infty} \dfrac{ b x^{b-1} }{ a ( \log x )^{a-1} 1/x } = \lim_{x \to \infty}\dfrac{ b x^b }{a (\log x )^{a-1} } = \cdots = \left( \frac{b}{a} \right)^a \lim_{x \to \infty} x^b = \infty.$$

I have two questions, first of all, is my work correct?

Secondly, why is showing this limit is $\infty$ is equivalent to proving $(\log x)^a = O( x^b ) $?

My thought is because to prove this $(\log x)^a = O( x^b ) $ we must show that

$$ (\log x)^a < C x^b,$$

for constant $C$ and so $\dfrac{x^b }{(\log x)^a } > 1/C $. Thus, if we know the above limit is infinite, we know the sequence is bounded so that there is some $K$ so that

$$\dfrac{x^b }{(\log x)^a } > K,$$

and so proves our assertment. IS this correct?

Answer 1

Answering your questions, one by one

1) It is correct, but incomplete. The expression just after '$\cdots$' is obtained only if $a$ is natural, otherwise the power of $\log x$ in the denominator will remain a fraction always. The general treatment is as follows. After '$\cdots$' you get, $$\lim_{x\to\infty}\dfrac{x^b}{(\log x)^a}=\left(\dfrac ba\right)^{\lfloor a\rfloor}\lim_{x\to\infty}\dfrac{x^b}{(\log x)^{\{a\}}}$$ Now, again appling L'Hospital rule, you get $$\text{Required limit}=\left(\dfrac ba\right)^{\lfloor a\rfloor+1}\lim_{x\to\infty}x^b(\log x)^{1-\{a\}}=\infty$$

2) Your reasoning is correct, but the statement that proving this and that is equivalent is a wrong statement. Proving that this limit is $\infty$ is a sufficient condition to show that $(\log x)^a = O(x^b)$, but not necessary, for example, $x^b = O(x^b)$ but the limit of their ratio is $1$.

Answer 2

For you first question, it isn't correct, for two reasons:

• Repeatedly applying L'Hospital would yield: $$\lim_{x \to \infty}\dfrac{x^b}{(\log x )^a} =\lim_{x \to \infty}\dfrac{b x^b}{a (\log x )^{a-1}} = \lim_{x \to \infty}\dfrac{ b^2 x^b }{a (a-1)(\log x )^{a-2}} = \dotsm, $$

so, if after $k$ applications, you do obtain $b^k$ in the numerator, in the denominator, you have $a(a-1)\cdots(a-k+1)$.

• As a consequence, if $a$ is not a positive integer, the logarithm never disappears from the denominator.

A better approach consists is showing that the logarithm of this expression tends to $\infty$: $$ \log\biggl(\frac{x^b }{(\log x )^a}\biggr)= b\log x-a\log(\log x)=\frac ba\biggl(1-\frac{\log(\log x)}{\log x}\biggr), $$ and make the substitution $t=\log x$.