# How to prove that exponential grows faster than polynomial?

In other word, how to prove:

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

$$\lim_{n\rightarrow\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.

-
Have you tried expressing both in terms of the exponential? –  gary Aug 4 '11 at 1:41
You could write the exponential as an infinite polynomial power series. You could also see what happens when you take higher and higher order derivatives of $n^b$ and $a^n$: the polynomial vanishes by an order each time and the exponential is only multiplied by a constant factors ($ln a$) each time. –  jnm2 Aug 4 '11 at 2:36

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.

-
Could this really work? I mean $\lim_{n\rightarrow\infty}n = \infty$. How can I do the induction? –  ablmf Aug 4 '11 at 2:55
What you said is true, but I don't see how it enters the picture. As far as the induction process: when $k = 0$, you need to show $\lim_{n \to \infty} \frac{1}{a^n} =0$. As far as the induction step, assume that it holds for $k$, then show that it also holds for $k+1$ (Apply L'Hopital). This is pretty much the entire solution, but again, I will let you fill in the details. –  JavaMan Aug 4 '11 at 3:27
Oh, I didn't know L'Hopital before. So the induction is $lim_{n\rightarrow\infty}\frac{n^(k+1)}{a^n} = lim_{n\rightarrow\infty}\frac{(k + 1) n^k}{ln(a)a^n} = 0$. Is that right? –  ablmf Aug 4 '11 at 3:41
Yes that's right. Since $k+1$ and $\ln(a)$ are constants, we can pull them out of the limit to get $\frac{k+1}{\ln(a)}\lim_{n \to \infty} \frac{n^{k}}{a^n} = \frac{k+1}{\ln(a)} \cdot 0 = 0$. –  JavaMan Aug 4 '11 at 3:45
Also, I should point out that when using TeX, if you enclose your exponent with braces like "a^{2x}", it will exponentiation the entire term and it will look like $a^{2x}$. Without braces, you get $a^2x$. –  JavaMan Aug 4 '11 at 3:48

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

-
This is the simplest solution I can think of. –  Qiaochu Yuan Aug 4 '11 at 2:59
This is a special case of multiplicative telescopy. See my post here for much further discussion of this example. Similar ideas work more generally for hyperrational functions. –  Bill Dubuque Aug 4 '11 at 3:02
That means $lim_{n\rightarrow\infty}\frac{n^b}{a^n}=lim_{n\rightarrow\infty}\frac{(n+1)^b}{‌​a^(n+1)}$, so it must be zero. Is my understanding right? –  ablmf Aug 4 '11 at 3:18
Yes, that's one good way to understand it. –  Gerry Myerson Aug 4 '11 at 3:50
@GerryMyerson I’m just reading this right now, but that’s a bad way to understand it: It isn’t clear yet that the limit exists at all and for any converging sequence $\lim a_n = \lim a_{n+1}$ holds, so one cannot deduce anything about the limit from this or am I missing something? Maybe ablmf meant $\lim_{n → ∞} {n^b}/{a^n} = \lim_{n → ∞} {n^b}/{a^{n+1}}$? But here again you first need to know that the limit exists. –  k.stm Jun 2 '13 at 17:55

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

-
+1: I really, honestly and whole-heartedly think that this is the way to do this problem. From scratch. No l'Hospital, no properties of logarithms. Nothing shaky :-). Just the binomial theorem (or Bernoulli's inequality) to do the case $b=1$. –  Jyrki Lahtonen Aug 4 '11 at 8:03
This is an elegant proof that could easily be understood. I will one day I could solve these problems as well as you do. –  ablmf Aug 4 '11 at 14:04

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.

-
Oops, seems that I won't be able to understand this before I finish my calculus course. –  ablmf Aug 4 '11 at 2:59

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?

-
So the question becomes to prove $lim_{n\rightarrow\infty}(bln(n)-kn) = -\infty$ right? BTW, you made some typos. –  ablmf Aug 4 '11 at 2:58
Yes; I think too, if you use that ln(n) grows slower than n. I will check for typos. –  gary Aug 4 '11 at 3:46

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

-

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

-

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.

-

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.

-