calculus- limit includes polynomial

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.

-
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
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
– Martin Sleziak Oct 16 '11 at 8:58

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}

-
@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}|}\}}$.

-
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...

-
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

-