2
$\begingroup$

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.

  • 0
    See also http://math.stackexchange.com/questions/5546$8$/how-to-prove-that-exponential-grows-faster-than-polynomial2011-10-16

4 Answers 4

0

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

  • 0
    Answer on a PSQ2018-12-08
2

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

  • 0
    @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}}$.2011-03-30
0

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

  • 0
    @DJC: No need for that, since you posted the answer very shortly after I did.2011-03-29
0

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}$

  • 0
    I'm not one for spelling out all details, especially on a homework problem, but each implication and inequality was meant to hold for sufficiently large $x$, as the OP was worried about limits as $x \to \infty$.2011-03-31