Exponential Growth Versus Polynomial Growth

Why Compare Exponential and Polynomial Growth?

Some sequences have a polynomial factor that increases with \(n\), while another factor changes exponentially. For example, \(n^3\) grows as a power of \(n\), whereas \(2^n\) multiplies by \(2\) each time \(n\) increases by \(1\). At first, both factors may become large, so comparing their limits by appearance alone is not enough.

The key result is that, for a fixed base greater than \(1\), exponential growth eventually outpaces every fixed nonnegative integer power of \(n\). This lets us evaluate many sequence limits without expanding large powers or relying on a table of terms.

A Proof Using the Binomial Theorem

Write \(r=1+c\), where \(c=r-1>0\). The binomial theorem gives a useful lower bound for \(r^n=(1+c)^n\). Choose an integer \(m>d\). For \(n\ge 2m\), one term in the binomial expansion is \(\binom{n}{m}c^m\), and all terms are nonnegative. Therefore \(r^n\ge \binom{n}{m}c^m\).

To bound the binomial coefficient, write it as a product. When \(n\ge 2m\), every factor \(n-j\), for \(j=0,1,\ldots,m-1\), is at least \(n/2\). Thus \(\binom{n}{m}\ge \frac{(n/2)^m}{m!}\). Combining these inequalities gives a bound on the original sequence.

Since \(n^d\) and \(r^n\) are positive, dividing by the lower bound for \(r^n\) reverses its effect on the quotient in the appropriate way: a larger denominator gives a smaller quotient. Hence, for \(n\ge 2m\),

The constant \(\frac{2^m m!}{c^m}\) does not depend on \(n\), and \(d-m<0\). The right-hand side is therefore a constant times \(\frac{1}{n^{m-d}}\), which approaches zero by the limits of polynomial and rational sequences. The Squeeze Theorem now proves the claimed limit.

Worked Example: A Cubic Power Divided by \(2^n\)

Using the Result for a Polynomial Numerator

The theorem also applies when the numerator is a polynomial rather than a single power. Let \(P(n)=a_dn^d+\cdots+a_1n+a_0\), where \(d\) is fixed. For \(n\ge1\), each \(n^j\) with \(0\le j\le d\) is at most \(n^d\). The triangle inequality therefore gives \(|P(n)|\le Cn^d\), where \(C=|a_0|+\cdots+|a_d|\). For \(r>1\),

The Squeeze Theorem shows that \(\frac{P(n)}{r^n}\to0\), whether the polynomial takes positive or negative values. This bound is useful because it reduces a polynomial numerator to its highest power without requiring a separate limit calculation for every term.

When the Exponential Is in the Numerator

If \(r>1\), \(d\) is a nonnegative integer, and \(n\ge1\), then \(\frac{r^n}{n^d}\) is the reciprocal of the positive quantity \(\frac{n^d}{r^n}\). Since that quantity approaches zero, its reciprocal grows without bound. In precise terms, if \(M>0\), the limit \(\frac{n^d}{r^n}\to0\) ensures that for sufficiently large \(n\), \(0<\frac{n^d}{r^n}<\frac1M\). Taking reciprocals gives \(\frac{r^n}{n^d}>M\). This is exactly the definition that the sequence tends to \(+\infty\).

How the Base Changes the Comparison

The condition \(r>1\) matters. If \(r=1\), then \(\frac{n^d}{r^n}=n^d\), which does not approach zero when \(d>0\); for \(d=0\), it equals \(1\). If \(0<r<1\), then \(r^n\) decreases toward zero, so \(\frac{n^d}{r^n}\) does not tend to zero. Indeed, writing \(s=1/r>1\) gives \(\frac{n^d}{r^n}=n^d s^n\), which grows without bound for \(d\ge0\). The comparison theorem is specifically for a fixed base greater than one in the exponential denominator.

For a general polynomial numerator and \(r>1\), the bound by \(Cn^d\) proves that its quotient by \(r^n\) tends to zero. The same reasoning does not say that every expression involving a power and an exponential has the same limit: the location of the factors and the value of the base are essential.

A Common Mistake: Comparing Two Infinite Quantities

A tempting but incorrect argument is: “Both \(n^3\) and \(2^n\) approach infinity, so their quotient approaches \(1\).” Knowing that the numerator and denominator separately grow without bound does not determine the limit of their quotient. For this specific example, the quotient actually approaches zero, as the consecutive-term bound showed.

Another invalid shortcut is to treat the notation \(\infty/\infty\) as an arithmetic calculation. Infinity is not a real number that can be substituted into a fraction. Instead, identify the form as indeterminate and establish a comparison, such as the binomial lower bound or a ratio bound. These methods show which factor controls the limit and justify the conclusion.