Polylogarithm grows slower than polynomial proof

Question

In the CLRS book, there's this part, where it's shown that $$\lim_{n\to\infty}\frac{(n^b)}{(a^n)} = 0.$$ In the same chapter, it uses the aforementioned equation to prove that any logarithmic function grows slower than any polynomial one, thus, $$\lim_{n\to\infty}\frac{\log b^n}{ n^a}$$. It does that by substituting lgn for n and 2^a for a in the first equation. How is it allowed to substitute the terms and prove the latter equation.

Answer 1

Let $a_n:= \frac{\log b^n}{ n^a}$, then $a_n =\frac{n \log b}{ n^a}=\log b \frac{1}{n^{a-1}}.$

We can assume that $\log b \ne 0.$

Case 1: $a=1.$ Then $a_n \to \log b .$

Case 2: $a>1$. Then $a_n \to 0.$

Case 3: $a<1.$ Then $a_n \to \infty$, if $b>1$ and $a_n \to - \infty$, if $0<b<1.$

Answer 2

For those who looks for the proof and the search engine takes them to here. I provided it below.

Start from $$\lim_{n\to\infty}\frac{n^b}{a^n} = 0.$$ Substitute ${\lg n}$ for ${n}$ and ${2^a}$ for ${a}$, we have $$\lim_{n\to\infty}\frac{\lg^b n}{{(2^a)}^{\lg n}} = 0.$$ Then $$\lim_{n\to\infty}\frac{\lg^b n}{{(2^{\lg n})}^a} = 0.$$ Therefore, $$\lim_{n\to\infty}\frac{\lg^b n}{n^a} = 0.$$

Hence proved.

The reason why we can substitute ${\lg n}$ for ${n}$ can be explained by the definition of limit.

Let $f(x)$ be a function from $ℝ$ to $ℝ$.

The definition of $\lim_{x\to\infty}=A$ is that $$\forall\epsilon\gt0,\exists\delta\gt0\ni if\,n\in ℝ \,with\,n\gt\delta,\,then\,|f(x)-A|\lt\epsilon.$$

I assume you know that $$\lim_{n\to\infty}\frac{n^b}{a^n} = 0.$$

By definition, $$\forall\epsilon\gt0,\exists\delta\gt0\ni if\,n\in ℝ \,with\,n\gt\delta,\,then\,|\frac{n^b}{a^n}-0|\lt\epsilon.$$

Now substitute ${\lg n}$ for ${n}$, we have $$\forall\epsilon\gt0,\exists\delta\gt0\ni if\,\lg n\in ℝ \,with\,\lg n\gt\delta,\,then\,|\frac{\lg^b n}{a^{\lg n}}-0|\lt\epsilon.$$

Since if $\lg n\gt\delta$, $n\gt2^\delta$.

So take a new delta $\hat\delta = 2^\delta$, it becomes $$\forall\epsilon\gt0,\exists\hat\delta=2^\delta\gt0\ni if\,n\in ℝ \,with\,n\gt\hat\delta,\,then\,|\frac{\lg^b n}{a^{\lg n}}-0|\lt\epsilon.$$

Which is $$\lim_{n\to\infty}\frac{\lg^b n}{n^a} = 0.$$ The basic concept is that the substitution just change the way we take $\delta$.

And why we can substitute $2^a$ for $a$ is that they are both constant.