# Exponential Dominates Polynomial

Jump to navigation
Jump to search

## Theorem

Let $\exp$ denote the real exponential function.

For any fixed $k \in \N$ and $\alpha > 0$ there exists $N \in \N$ such that $x^k < \exp \left({\alpha x}\right)$ for all real $x > N$.

## Proof

Choose any $N > \dfrac{\left({k + 1}\right)!} {\alpha^{k+1}}$, where $!$ denotes the factorial.

By Taylor Series Expansion for Exponential Function we have for any $x \in \R_{\ge 0}$:

- $\displaystyle \exp \left({\alpha x}\right) = \sum_{m \mathop \ge 0} \frac{\left({\alpha x}\right)^m}{m!} > \frac{\left({\alpha x}\right)^{k+1}}{\left({k + 1}\right)!}$

Therefore, for any $x > N$ we have:

\(\displaystyle \exp \left({\alpha x}\right)\) | \(>\) | \(\displaystyle \frac{\left({\alpha x}\right)^{k+1} } {\left({k + 1}\right)!}\) | |||||||||||

\(\displaystyle \) | \(>\) | \(\displaystyle \frac{N \alpha^{k+1} } {\left({k + 1}\right)!} x^k\) | because $x > N$ | ||||||||||

\(\displaystyle \) | \(>\) | \(\displaystyle x^k\) | by definition of $N$ |

This establishes the result.

$\blacksquare$