How to Show Polynomial Growth < Exponential Growth (Without L'Hopital!)

Question

Can anyone offer me a way to show that exponential growth trumps polynomial growth, without using L'Hopital's Rule? When I learned function growth speeds in high school, the closest thing to a proof I got was using L'Hopital- is there another way, that would make sense to someone who does not know of calculus?

Also, I want more than just a graphical proof!

Answer 1

Theorem: let $p \in \mathbb{Z^+}$ and $\alpha \in (0,1)$ be constant. Then $a_n=n^p\alpha^n\to0.$

$\underline{\text{Proof}}$

Consider the series $\sum\limits_{n=1}^{\infty}a_n$.

Then we have $$\frac{a_{n+1}}{a_n}=\frac{(n+1)^p\alpha^{n+1}}{n^p \alpha^n}=\left(1+\frac{1}{n}\right)^p\alpha \to \underbrace{\alpha<1}_{\text{by assumption}}.$$

Therefore $\sum\limits_{n=1}^{\infty}a_n$ converges (by the Ratio Test), so $a_n \to 0$ by the Divergence Test. $\square$

Answer 2

Just as you prove the convergence of the geometric sequence you can also prove the convergence to zero if you multiply by a polynomial factor.

Consider a sequence $p(n)\cdot q^n$ with a polynomial $p$ (with positive coefficients) of degree $d$ and $0<q<1$. Then $q=\frac1{1+α}$ with $α>0$. Using binomial expansion and removing some positive terms in the denominator one finds $$ \frac{p(n)}{(1+α)^n}=\frac{p(n)}{1+nα+\binom n2 α^2+...+α^n}\le\frac{p(n)}{1+\binom{n}{d+1}α^{d+1}}. $$ The denominator of the bound is a polynomial of degree $d+1$ in $n$ and thus faster growing than the numerator.