Prove asymptotic bound? Prove: 
$$n^b = \mathcal{o}(a^n)$$
for and constants $b$ and $a$, where $a > 1$. The book states that:
$$\lim_{ n \rightarrow \infty} \frac{n^b}{a^n} = 0$$
The book doesn't prove the limit though. Thanks for the help.
 A: That is one way to prove that exponential complexity ($a^n$) is always greater than polynomial complexity ($n^b$). Here is the formal definition of the statement $n^b$ is $o(a^n)$:
$$n^b \text{ is } o(a^n) \iff \{\forall c>0,n>n_0: |n^b| < c|a^n| \}$$
$$ \frac{n^b}{a^n} < c $$
$$ \frac{a^{b \log_a(n)}}{a^{n}}< c \quad (\text{Since }n=a^{\log_an})$$
$$ a^{b \log_a(n)-n} < c $$
This is expression is true since $\lim_{n \rightarrow \infty} a^{b \log_a(n)-n} = 0$. 
$$\therefore n^b \text{ is } o(a^n)$$
The limit from the book should be: $$\lim_{n \rightarrow \infty} \frac{n^b}{a^n} = 0$$
which shows that $a^n$ dominates the expression $n^b$ (definition of little o). Hope this helps!
A: You are right. The correct statement should be
$$ \lim_{n\to\infty}\frac{n^b}{a^n}=0 $$
for any constants $a,b$ and $a>1$. For $b\le 0$, it is trivial. For $b>0$, let $m$ be an integer such that $0\le m\le k<m+1$. Let $c=a-1>0$. Since, for $n>m+1$,
$$ a^n=(1+c)^n=\sum_{k=0}\binom{n}{k}c^k\ge \binom{n}{m+1}c^{m+1} $$
we have
$$0<\frac{n^b}{a^n}<\frac{n^b}{\binom{n}{m+1}c^{m+1}}. $$
It is easy to check 
$$\lim_{n\to\infty}\frac{n^b}{\binom{n}{m+1}}=0. $$
Thus
$$ \lim_{n\to\infty}\frac{n^b}{a^n}=0. $$
