1
$\begingroup$

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!

$\endgroup$
1
0
$\begingroup$

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$

$\endgroup$
6
  • 1
    $\begingroup$ This does not answer the question and is not a valid proof. You only consider integer values of $n$. You can see how all of the proofs in this thread answer the question without relying on an integer $n$. Consider revising. $\endgroup$ – Brad Jul 2 '14 at 21:37
  • $\begingroup$ @Brad Hi, Brad. Lovely to speak to you again. Too bad your serial downvoting has proved fruitless, but, ah, well; at least you tried. I'd love to take your advice, but mine is a perfectly-acceptable answer, and I'm going to decline. $\endgroup$ – beep-boop Jul 2 '14 at 22:08
  • $\begingroup$ Tip: There is an easy method to determine which user has downvoted you. It is not me. Another tip: It is very funny that you accuse me of serial downvoting when you are the one guilty of it. I find it funny that you still hold a grudge when I corrected another answer you posted 10+ days ago. Are you blaming me for making sure people understand mathematics correctly? The reason this post does not work is because you only consider integer values of $n$. $\endgroup$ – Brad Jul 3 '14 at 0:02
  • $\begingroup$ @Brad Do you have any evidence to suggest that I'm guilty of it? True- my proof is valid for all $n \in \mathbb{N}.$ And what's this method of determining who's downvoted me (without my having any suspicion), out of curiosity? $\endgroup$ – beep-boop Jul 3 '14 at 0:13
  • $\begingroup$ As I just said, there is a method of determining which user has downvoted your posts. Serial voting does not accomplish anything because the votes will just be reversed. I hope you can see this now. And yes, serial voting can be detected even if multiple accounts are used and even if the voting is spread out over time. It can also lead to account suspension. There is no reason to do it. $\endgroup$ – Brad Jul 7 '14 at 19:08
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy