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!
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.