TITLE: How to Show Polynomial Growth < Exponential Growth (Without L'Hopital!)
QUESTION [1 upvotes]: 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!

REPLY [0 votes]: 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.
{"set_name": "stack_exchange", "score": 1, "question_id": 854051}