Saturday, June 2, 2018

limits - Proving that a quasi-polynomial grows faster than any polynomial


I am trying to prove that given a quasi-polynomial $x^{\ln x}$ grows faster (at infinity) than any regular old polynomial of the form $x^a$ where $a \in \mathbb{R}$.



I reduced this problem to showing that $$ \lim_{x \to \infty} \frac{n^a}{n^{\ln n}} = 0. $$


When trying to compute the limit I cannot find a way to continue:


$$ \lim_{x \to \infty} \frac{x^a}{x^{\ln x}} = \lim_{x \to \infty} \Big(\frac{x}{x^{(\ln x) / a}}\Big)^a = \Big[\lim_{x \to \infty} \frac{x}{x^{(\ln x) / a}}\Big]^a. $$


Where can I go from here? I know how to show this intuitively ($(\ln x)/a \to \infty$ as $x \to \infty$) so the degree in the denominator is bigger than the degree in the numerator, but how would I prove it knowing only limit laws?


Answer



Use exponentiation.


$$ \lim_{x \to \infty} \frac{x^a}{x^{\ln x}} = \lim_{x \to \infty} x^{a-\ln x} =\lim_{x \to \infty}e^{(a-\ln x )(\ln x)} = e^{\lim_{x \to \infty} (a-\ln x)(\ln x)}= e^{ \to -\infty}\to 0 $$


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...