Polylogarithm grows slower than polynomial proof 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. 
 A: 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.$
A: 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.
