Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Good morning,

I would like your help with proving that

$$\lim_{n \to \infty} \frac{e^n}{P(n)} = \infty,$$

where $P(n)$ is a polynomial of degree at least $1$.

Thank you very much.

share|improve this question
    
I tried: bounding the limit, trying to find an expression that is smaller than this one and tends it's limit is also infinty. and All kind of arithmetics. –  user6163 Mar 29 '11 at 10:48
1  
If you know L'Hospital's rule, you can apply it here. Different possibility: You just need to find the limit of e^n/n^k, where k is the degree of your polynomial. By choosing n large enough - such that say (n+1)^k/n^k<2 - you get $e^n/n^k \ge C.(e/2)^n$, where C is some constant depending on k. –  Martin Sleziak Mar 29 '11 at 11:26
    
@Martin: I'm not allowed to use L'hopital here, Can you extend a bit your second suggestion? –  user6163 Mar 29 '11 at 13:29
    

4 Answers 4

up vote 0 down vote accepted

Write $P(x) = \displaystyle\sum_{n=0}^k a_n x^n$, and note $|P(x)| \leq k|a_k|x^k$ for all $x \geq 1$.

Hint:

$$\begin{align} |P(x)| \leq C_k x^k &\Longrightarrow \log P(x) \leq \log (C_k x^k) \\ &\Longrightarrow \log P(x) \leq C_k + k \log x \\ &\Longrightarrow \log P(x) \leq x \\ &\Longrightarrow P(x) \leq e^{x} \end{align}$$

share|improve this answer
    
@DJC: can you please show me how to finish this? –  user6163 Mar 29 '11 at 16:10
    
@Nir: I don't understand what you mean. I gave sufficiently many (maybe too many) hints. What's not to see? Is there a particular step which is difficult, or are you just uncomfortable with writing down the details? –  JavaMan Mar 29 '11 at 16:10
    
@DJC:I just can't see how from the last inequalit that you got the the proof is shown. –  user6163 Mar 29 '11 at 16:26
    
These inequalities in fact do not prove your statement, but they should give you a vague idea about how to proceed...By the way, why exactly are you not allowed to use L'Hopital's rule here? –  JavaMan Mar 29 '11 at 16:35
    
@DJC: Ok, now with your edit, it is more clear. I can't use use lopital, because in those exrecies I'm not allowed to. eventhough I studied that in the past and I know that, I want to study in a constructive way. –  user6163 Mar 29 '11 at 17:00

Assume that $p(x) = a_{n}x^n + \cdots + a_1 x + a_0$ with $a_{n} \neq 0$ and $n \geq 1$.

Claim. For $|x|$ large enough we have $|p(x)| \leq 2|a_{n}||x|^n.$

On the other hand we see that $e^x \geq \frac{x^{n+1}}{(n+1)!}$ for $x \geq 0$ from the defining series of $e^x$. Using the claim thus gives $$ \left\vert \frac{e^x}{p(x)}\right\vert \geq \frac{|x|}{2|a_{n}|(n+1)!}$$ from which $\left\vert \frac{e^x}{p(x)}\right\vert \; \xrightarrow{x \to \infty} \; \infty$ follows immediately (in writing up your own solution be careful with the sign of $a_{n}$)!

To see the inequality $|p(x)| \leq 2|a_{n}||x|^n$ note that for $|x| \geq 1$ we have $|x|^{n-1} \geq |x|^k$ for $k = 0, \ldots, n-1$ so that $$ |p(x)| \leq |a_{n}||x|^n + |a_{n-1}||x|^{n-1} + \cdots + |a_1||x| + |a_{0}| \leq |a_{n}||x|^n + (|a_{n-1}| + \cdots + |a_{0}|)|x|^{n-1} $$ and it is now easy to check that the claimed inequality holds for $|x| \geq \max{\{1,\frac{|a_{n-1}| + \cdots + |a_{0}|}{|a_{n}|}\}}$.

share|improve this answer
    
thank you very much for the answer. Is there any other solution that you may think about that does not involve the inequality of e^x from taylor series? I can't use it here. –  user6163 Mar 29 '11 at 13:18
    
@Nir: You can also use that $e^x \geq (1+\frac{x}{n+1})^{n+1}$ so that $e^x \geq \frac{x^{n+1}}{(n+1)^{n+1}}$. –  t.b. Mar 30 '11 at 6:08

Write $n=e^x$ to conclude that it suffices to show that $e^x > x^2$ for all $x$ sufficiently large. Now, take $\log$s...

share|improve this answer
    
If you feel my answer is too close to your hint, I'll gladly erase it. –  JavaMan Mar 29 '11 at 15:14
    
@DJC: No need for that, since you posted the answer very shortly after I did. –  Shai Covo Mar 29 '11 at 15:22

Since limit of $P(n)/n^k$ is finite (k being the degree), it suffices to show that $e^n/n^k$ tends to infinity. Since $\lim_{n\to\infty} \frac{(n+1)^k}{n^k}=1$, there exists $n_0$ such that $n>n_0$ implies $\frac{(n+1)^k}{n^k}\le 2$. From this you can easily see (or show by induction) that $\frac{e^n}{n^k} \ge \frac{e^{n_0}}{n_0^k} \left(\frac2e\right)^{n-n_0}$ whenever $n\ge n_0$. (Just notice the quotient of two consecutive terms.)

Hence $\frac{e^n}{n^k}=C_k \left(\frac2e\right)^n$, where $C_k$ is a constant depending on $n_0$ (and thus on $k$) but not on $n$. This is what I had in mind when I posted the above comment. And it's pretty intuitive too - you simply compare the $n^k$ to the geometric progression by comparing the quotients

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.