How to prove that exponential grows faster than polynomial?

Question

In other words, how to prove:

For all real constants $a$ and $b$ such that $a > 1$,

$$\lim_{n\to\infty}\frac{n^b}{a^n} = 0$$

I know the definition of limit but I feel that it's not enough to prove this theorem.

Answer 1

We can confine attention to $b \ge 1$. This is because, if $0<b<1$, then $n^b \le n$. If we can prove that $n/a^n$ approaches $0$, it will follow that $n^b/a^n$ approaches $0$ for any positive $b\le 1$. So from now on we take $b \ge 1$.

Now look at $n^b/a^n$, and take the $b$-th root. We get $$\frac{n}{(a^{1/b})^n}$$ or equivalently $$\frac{n}{c^n}$$ where $c=a^{1/b}$.

Note that $c>1$. If we can prove that $n/c^n$ approaches $0$ as $n\to\infty$, we will be finished.

For our original sequence consists of the $b$-th powers of the new sequence $(n/c^n)$. If we can show that $n/c^n$ has limit $0$, then after a while, $n/c^n \le 1$, and so, after a while, the old sequence is, term by term, $\le$ the new sequence. (Recall that $b\ge 1$.)

Progress, we need only look at $n/c^n$.

How do we continue? Any of the ways suggested by the other posts. Or else, let $c=1+d$. Note that $d$ is positive. Note also that from the Binomial Theorem, if $n \ge 2$ we have $$c^n=(1+d)^n \ge 1+dn+d^2n(n-1)/2\gt d^2(n)(n-1)/2.$$

It follows that $$\frac{n}{c^n}< \frac{n}{d^2(n)(n-1)/2}=\frac{2}{d^2(n-1)}.$$ and it is clear that $\dfrac{2}{d^2(n-1)} \to 0$ as $n\to\infty$.

Answer 2

We could prove this by induction on integers $k$:

$$ \lim_{n \to \infty} \frac{n^k}{a^n} = 0. $$

The case $k = 0$ is straightforward. I will leave the induction step to you. To see how this implies the statement for all real $b$, just note that every real number is less than some integer. In particular, $b \leq \lceil b \rceil$. Thus,

$$ 0 \leq \lim_{n \to \infty} \frac{n^b}{a^n} \leq \lim_{n \to \infty} \frac{n^{\lceil b \rceil}}{a^n} = 0. $$

The first inequality follows since all the terms are positive. The last equality follows from the induction we established previously.

Answer 3

First, notice that $(n+1)^b/n^b=1$ plus terms in negative powers of $n$, so it goes to 1 as $n\to\infty$ (with $b$ fixed). Now going from $n^b/a^n$ to $(n+1)^b/a^{n+1}$, you multiply the numerator by something that's going to 1 but the denominator by something that isn't (namely, by $a\gt1$).

Answer 4

You can expand as$$a^n = e^{n\log a} = 1+n\log a +\cdots +\frac{(n\log a)^b}{b!}+\cdots$$

$$\frac{a^n}{n^b} =\frac{1}{n^b}+\frac{1}{n^{b-1}}\log a+\cdots+\frac{(\log a)^{b}}{b!}+n\frac{(\log a)^{b+1}}{(b+1)!}+\cdots $$ So, $$\frac{a^n}{n^b}\geq n\frac{(\log a)^{b+1}}{(b+1)!}$$. This becomes arbitrarily large with large $n$

Therefore, $$\lim_{n\rightarrow\infty}\frac{a^n}{n^b} = \infty$$ Or $$\lim_{n\rightarrow\infty}\frac{n^b}{a^n} = 0$$

Answer 5

Regard the exponential function as the unique solution to the initial value problem $f(0) = 1$ with $f' = f$. The equivalent integral formulation is

$f(t) = 1 + \int_0^t f(s) ds$

First prove that $f$ is an increasing function. For $t \geq 0$, you can use a method of continuity argument by considering the set $\{ s ~:~ f \mbox{ increases on } [0, s] \}$. The supremum of this set cannot be finite. For $s < 0$ you can also consider the ODE satisfied by $f^2$, but you're not really concerned with that. Now that we know $f$ increase, we also know $f$ grows at least linearly:

$f(t) \geq 1 + \int_0^t 1 ds = (1 + t)$

It also grows at least quadratically..

$f(t) \geq f(\frac{t}{2}) + \int_{t/2}^t f(s) ds \geq (1 + t/2) f(t/2)$

And repeating yields

$f(t) \geq (1 + t/2)^2$

In general, $f(t) \geq (1 + t/n)^n$ by the same method. It's even true for $n$ not an integer. In this case, the function $(1 + t/n)^n$ is defined in the first place to be $e^{n \log( 1 + t/n) }$. Then, since log x is defined by the integral $\int_1^x \frac{1}{t} dt = x \int_0^1 (1 + sx)^{-1} ds $, we can rewrite

$(1 + t/n)^n = e^{n \log (1 + t/n) } = \mbox{exp}(t \int_0^1 (1 + \frac{s t}{n})^{-1} ds ) \leq e^t$

EDIT: This answer may not be so helpful to you. I didn't read the end of your question, so you may not know how to work with most of the things I've been writing about. The main reason why the exponential grows faster than a polynomial is because if $f$ is exponential, then $f(n+1)$ is at least a constant times $f(n)$, whereas when $f$ is a polynomial, $f(n+1)$ is roughly the same size as $f(n)$ when $n$ is large. After all, you can hardly tell the difference between the volume of a huge cube, and a huge cube 1 unit longer in each direction.

Answer 6

Try expressing both in terms of the exponential $e^x$: $n^b$=$e^{bln(n)}$; $a^n=e^{nln(a)}$, so that the quotient becomes:

$\frac{n^b}{a^n}$= $\frac{e^{bln(n)}}{e^{nln(a)}}=e^{bln(n)-nln(a)}=e^{bln(n)-kn}=\frac{e^{nlna}}{e^{kn}}$ , where k is a real constant. Can you tell which of ln(n) or n grows faster?

Answer 7

This is inspired by André Nicolas's answer, but instead of taking $b^{th}$ roots, I'll take $n^{th}$ roots.

The limit of the sequence of $n^{th}$ roots of the terms in the original sequence is $$\lim_{n\to\infty}\frac{(n^b)^{1/n}}{a}=\lim_{n\to\infty}\frac{\left(n^{1/n}\right)^b}{a}=\frac{\left(\lim\limits_{n\to\infty} n^{1/n}\right)^b}{a}=\frac{1^b}{a}=\frac{1}{a}.$$

(I used here the fact that $\lim\limits_{n\to\infty}n^{1/n}=1$, which was the subject of another question on this site, and which can also be proved in many ways.)

If $c$ is any number such that $\frac{1}{a}<c<1$, then the previous limit implies that there is an $N>0$ such that for all $n>N$, $$\left(\frac{n^b}{a^n}\right)^{1/n}\lt c.$$ Then for all $n>N$, $$\frac{n^b}{a^n}\lt c^n.$$ Since $c^n\to 0$, this shows that the original series goes to zero.

Alternatively, once you know that the sequence of $n^{th}$ roots converges to a number less than $1$, you can apply the root test to conclude that $\sum\limits_{n=1}^\infty\frac{n^b}{a^n}$ converges, which implies that the terms go to $0$. (The proof of the root test actually just uses the inequality derived above and the convergence of the geometric series with common ratio $c$.)

Answer 8

Since it is almost always better to expand around zero, let $a = 1+c$, where $c > 0$. So we want to show $\lim \frac{n^b}{(1+c)^n} = 0$.

The ratio of consecutive terms is $\frac{(1+1/n)^b}{1+c}$, so if we can show that $(1+1/n)^b < 1+c/2$ for large enough n, we are done. But this means that $n > 1/((1+c/2)^{1/b}-1)$.

Restating, letting $N = \frac{1}{(1+c/2)^{1/b}-1}$ and $r = \frac{1+c/2}{1+c}$, if $n > N$ then $\frac{(1+1/n)^b}{1+c} < \frac{1+c/2}{1+c}$, which shows that $$ \frac{n^b}{(1+c)^n} < \frac{N^b}{(1+c)^N}r^{n-N}$$ which goes to $0$ as $n \rightarrow \infty$ since $N$ is fixed and $0 < r < 1$.

Note: An elementary proof that $r^n \rightarrow 0$ is in "What is Mathematics?" by Courant and Robbins.

Let $r = 1/(1+s)$, where $s > 0$. By Bernoulli's inequality, $$r^n = \frac{1}{(1+s)^n} < \frac{1}{1+s\ n} = \frac{1}{1+ n (1/r-1)}.$$ They similarly show that, if $a > 1$, then $a^n \rightarrow \infty$ like this: Let $ a = 1+b$, where $b > 0$. Then $$a^n = (1+b)^n > 1+n\ b = 1+n(a-1).$$ The keys in both these are expanding around zero and using Bernoulli's inequality. Archimede's axiom (for any positive reals $x$ and $y$, there is an integer $n$ such that $x < n\ y$) does the rest.

Answer 9

Rudin states this as a theorem in his Principle of Mathematical Analysis. See Theorem 3.20 (d) on page 57 of the 3rd edition.

This theorem is in Chapter 3 Numerical Sequences and Series of the book, way before the definition of derivatives and even before the discussion of continuous functions. Rudin's presentation is very succinct and reads like a poem:

Theorem 3.20 (d). If $p>0$ and $\alpha$ is real, then $\displaystyle\lim_{n\to\infty}\frac{n^\alpha}{(1+p)^n}=0$.

Proof. Let $k$ be an integer such that $k>\alpha$, $k>0$. For $n>2k$, $$ (1+p)^n>\binom{n}{k}p^k=\frac{n(n-1)\cdots(n-k+1)}{k!}p^k>\frac{n^kp^k}{2^kk!}. $$ Hence $$ 0<\frac{n^\alpha}{(1+p)^n}<\frac{2^kk!}{p^k}n^{\alpha-k}\quad (n>2k). $$ Since $\alpha-k<0$, $n^{\alpha-k}\to 0$, by (a).^†

---

† Here (a) is a statement in Theorem 3.20, which says that

if $p>0$, then $\displaystyle \lim_{n\to\infty}\frac{1}{n^p}=0$.

The proof of this fact in Rudin is of one line: Take $n>(1/\varepsilon)^{1/p}$. The author also makes a comment that "Note that the archimedean property of the real number system is used here."

Answer 10

Tom Apostol, in volume I of his 2-volume text on calculus, gives what I consider to be the canonical proof of this assertion. He calls it the theorem of “the slow growth of the logarithm”. By making the appropriate substitution (namely, exp(x) for x), you can get what we can call the theorem on “the fast growth of the exponential”.

I think you will have no difficulty agreeing that as far as comparing a polynomial to the exponential goes, the only part of the polynomial that we have to consider is the term involving the highest power, and that we can even disregard its coefficient. (This agreement is currently shown in your question, but I believe that is the result of someone else’s edit, and so I am answering what I believe your original question was.) That is what that theorem in Apostol does: it shows that if a > 0 and b > 0, then the limit as x goes to infinity of ((log(x))^a)/(x^b) goes to 0.

You might be interested is knowing a significant application of this fact, namely, in the proof of the recursion formula for what is known as the Gamma function (which is the canonical continuous extension of the factorial function but, for historical reasons, shifted one unit). That is, in proving that Gamma(x + 1) = xGamma(x), one typically applies the technique of integration-by-parts, and one piece of the resulting expression is a power divided by an exponential, which goes to 0 as one takes the limit as the upper limit of the integral goes to infinity.

Another application of this fact is the shape of the graph of y = x*exp(x), namely, that as x goes to negative infinity, y goes to 0.

Answer 11

The case $ b\le 0$ is blatantly obvious since $n^b \le 1$ for $b\le 0$ and hence since $a>1$ we have, $$\frac{n^b}{a^n} \le \frac{1}{a^n} =\left(\frac{1}{a}\right)^n\to 0$$

we assume $ b>0$ then,

$$\frac{n^b}{a^n}=\left(\frac{b}{\ln a} \right)^b\left(n\frac{\ln a}{b} e^{-n\frac{\ln a}{b}}\right)^b \color{red}{\overset{u= n\frac{\ln a}{b}}{:=}\left(\frac{b}{\ln a} \right)^b\left(u e^{-u}\right)^b} ~~~~ b>0,~~$$

Hence, $$\lim_{n\to\infty}\frac{n^b}{a^n}= \lim_{u\to\infty}\left(\frac{b}{\ln a} \right)^b\left(u e^{-u}\right)^b=0$$

Answer 12

As several of the previous answers have noted it is enough to show that $\lim_{x\to \infty} \frac{x}{a^x}=0$. To prove this, in turn it is enough to prove that $\lim_{x \to \infty} \frac{a^x}{x} = \infty$.

Lets compute the derivative and second derivative of $f(x) = \frac{a^x}{x}$. We find that $f'(x) = \frac{a^x(x \ln(a)-1)}{x^2}$ and $f''(x) = \frac{a^x(x^2 \ln^2(a)-2\ln(a) x+2)}{x^3}$.

We see that for large enough values of $x$, both $f'(x)$ and $f''(x)$ are positive. Thus, $f$ not only grows, it grows at an increasing rate. The only possible conclusion is that $\lim_{x\to \infty} \frac{a^x}{x} = \infty$.

With a little work this can be made into a completely rigorous proof.

Answer 13

Another method is the following (this method was originally? used by W. Rudin in his PMA):

For $n\geqslant2(|\lceil b\rceil|+1)$ (the absolute value of the ceiling of $b$) we have, using the binomial theorem:$$\begin{aligned}a^n&=(1+(a-1))^n\\\\&>\binom{n}{|\lceil b\rceil|+1}(a-1)^{|\lceil b\rceil|+1}\\\\&=\dfrac{n(n-1)\cdots(n-|\lceil b\rceil|)}{(|\lceil b\rceil|+1)!}(a-1)^{|\lceil b\rceil|+1}\\\\&>\dfrac{n^{|\lceil b\rceil|+1}}{2^{|\lceil b\rceil|+1}(|\lceil b\rceil|+1)!}(a-1)^{|\lceil b\rceil|+1}\end{aligned}$$ so $$\left(\dfrac{2^{|\lceil b\rceil|+1}(|\lceil b\rceil|+1)!}{(a-1)^{|\lceil b\rceil|+1}}\right)\cdot\dfrac{1}{n}>\dfrac{n^{|\lceil b\rceil|}}{a^n}\geqslant\dfrac{n^b}{a^n}$$ and hence $$\lim_{n\to\infty}\dfrac{n^b}{a^n}=0.$$

Answer 14

You could also see the following: $$\lim_{n\rightarrow\infty}\frac{n^b}{a^n} = \lim_{n\rightarrow\infty}e^{\log \frac{n^b}{a^n}}$$

Now $\lim_{n\rightarrow\infty}\log (\frac{n^b}{a^n})=\lim_{n\rightarrow\infty}(\log (n^b) - \log (a^n))=\lim_{n\rightarrow\infty} (b\log(n)-n\log(a))=-\infty$ assuming $a>1$.

So $\lim_{n\rightarrow\infty}e^{\log \frac{n^b}{a^n}}=0=\lim_{n\rightarrow\infty}\frac{n^b}{a^n}$

Just to clarify the comment, I am adding the proof that $$\lim_{n\rightarrow\infty} (b\log (n)-n\log (a))=-\infty$$

First by applying L'Hôpital's rule we get

$$\lim_{n\rightarrow\infty} \frac{n}{\log(n)}=\lim_{n\rightarrow\infty} \frac{1}{\frac{1}{n}} \to \infty$$ We have then $$\lim_{n\rightarrow\infty} (b\log (n)-n\log (a))=\lim_{n\rightarrow\infty} \log(n)(b-\log(a)\frac{n}{\log(n)})=-\infty$$

Answer 15

We have

$$\frac{n^b}{a^n}=e^{b\log n-n\log a}=e^{-n\left(\log a-b\frac{\log n}{n}\right)}\to 0$$

indeed

• $\log a-b\cdot \frac{\log n}{n} \to \log a-b\cdot 0=\log a>0$

and therefore

• ${n\cdot \left(\log a-b\cdot \frac{\log n}{n}\right)}\to \infty$

For $\frac{\log n}{n}\to 0$ refer to Prove $\log(x) \lt x^n$ for all $n \gt 0$.