Is 'every exponential grows faster than every polynomial?' always true?

Question

My algorithm textbook has a theorem that says

'For every $r > 1$ and every $d > 0$, we have $n^d = O(r^n)$.'

However, it does not provide proof.

Of course I know exponential grows faster than polynomial in most cases, but is it true for all case?

What if the polynomial function is something like $n^{100^{100}}$ and exponential is $2^n$? Will the latter outgrow the former at some point?

Answer 1

Yes, it is true for all cases. This can be seen by noting that

$$\lim_{n\to\infty} \frac{n^k}{e^n} = 0$$

for any $k$. This can be seen by an application of L'Hospital's rule a number of times, or by using induction as here.

Answer 2

Hint: Yes. See Taylor expansion of exponential function.