Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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!
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$
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.
