How to prove that exponential grows faster than polynomial?

In other words, how to prove:

For all real constants $a$ and $b$ such that $a > 1$,

$$\lim_{n\to\infty}\frac{n^b}{a^n} = 0$$

I know the definition of limit but I feel that it’s not enough to prove this theorem.

Answer

We can confine attention to $b \ge 1$. This is because, if $0<b<1$, then $n^b \le n$. If we can prove that $n/a^n$ approaches $0$, it will follow that $n^b/a^n$ approaches $0$ for any positive $b\le 1$. So from now on we take $b \ge 1$.

Now look at $n^b/a^n$, and take the $b$-th root. We get
$$\frac{n}{(a^{1/b})^n}$$
or equivalently
$$\frac{n}{c^n}$$
where $c=a^{1/b}$.

Note that $c>1$. If we can prove that $n/c^n$ approaches $0$ as $n\to\infty$, we will be finished.

For our original sequence consists of the $b$-th powers of the new sequence $(n/c^n)$. If we can show that $n/c^n$ has limit $0$, then after a while, $n/c^n \le 1$, and so, after a while, the old sequence is, term by term, $\le$ the new sequence. (Recall that $b\ge 1$.)

Progress, we need only look at $n/c^n$.

How do we continue? Any of the ways suggested by the other posts. Or else, let
$c=1+d$. Note that $d$ is positive. Note also that from the Binomial Theorem, if $n \ge 2$ we have
$$c^n=(1+d)^n \ge 1+dn+d^2n(n-1)/2\gt d^2(n)(n-1)/2.$$

It follows that
$$\frac{n}{c^n}< \frac{n}{d^2(n)(n-1)/2}=\frac{2}{d^2(n-1)}.$$
and it is clear that $\dfrac{2}{d^2(n-1)} \to 0$ as $n\to\infty$.

Attribution
Source : Link , Question Author : ablmf , Answer Author : André Nicolas

Leave a Comment