Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Proof by Contradiction: e^n....


Date: 7/5/96 at 10:8:22
From: Scott Turner
Subject: Proof by Contradiction: e^n....

I'm trying to prove that e^n (n is a natural number) is not O(n^m) for 
any power of m.  Note: e^n = 1 + n + n2/2!+ ....

I've begun by attempted that the e^n is O(n^m) in which case there is 
a constant C such that e^n <= Cn^m.

Next I took the natural log of both sides, which resulted in
n <= ln C + mln N.  From there I don't think that I can say my 
assumption is false but I'm stuck.

Thanks.

ST


Date: 7/8/96 at 9:42:5
From: Doctor Richard
Subject: Re: Proof by Contradiction: e^n....

Hi Scott,

That idea of taking ln of both sides was a reasonable thing to try, 
but in this case it leaves you with an equivalent problem because you 
need some sort of approximation of  ln(n)  in order to derive a 
contradiction from your inequality.

Instead, I think the simplest way to get this result is to compare  
n^m  with n^(m   1)  and realize that the second of these must 
eventually overwhelm the first, no matter what positive constants 
those are multiplied by.  By "eventually", I mean for large enough n.  
(Actually, to prove that  e^n  is not O(n^m), it suffices merely to 
show that for any constant C > 0,  e^n > C n^m   for certain 
arbitrarily high values of  n; but in this case showing it for _all_ 
sufficiently high  n  just "comes for free").

So, do you see where I'm going?  Just observe that  

    n^(m + 1)/(m + 1)! < e^n

for all positive  n, because that's just one of the terms in the 
series and all the terms are positive.  So if you're assuming that  
e^n < C n^m  for all sufficiently large  n, we get

    n^(m + 1)/(m + 1)! < C n^m

for all sufficiently large  n.   Remember that  m  here is fixed 
(though arbitrary).  I think you can see how to finish getting a 
contradiction from this.   So  e^n  can't be O(n^m) after all.


In a nutshell:  e^n  is a "sum of all non-negative integer powers of  
n  (with coefficients)", so no single one of those powers can be the 
dominant term in the sum. 

-Doctor Richard,  The Math Forum
 Check out our web site!
    
Associated Topics:
High School Discrete Mathematics

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/