How can I prove that eventually one function will overtake another, and find when?

Question

Given for example 2 functions,$\ n^{100} $ and$\ 2^n$. I know that$\ 2^n$ grows faster and that therefore there is some$\ n$ where it will eventually overtake $\ n^{100} $ but how can I prove this, and also maybe find that$\ n$?

Answer 1

One elementary way of proving that exponentials grow faster is to use the binomial expansion.

To illustrate, here $(1+1)^r=1+r+\binom r2+\binom r3+\dots$, where we can choose $r$ large enough for all the terms we need to exist on the right-hand side.

To show that $2^r$ is eventually larger than $r^2$ we take the term $\binom r3=\frac {r(r-1)(r-2)}{3!}$ from the expansion and observe that this is a cubic in $r$ with positive leading term, and is therefore eventually greater than any quadratic in $r$ with positive leading term, and hence eventually greater that $r^2$. Since this is just one of the positive terms on the right-hand side, we have for large enough $r$ $$2^r=(1+1)^r\gt\binom r3\gt r^2$$ with some very crude estimates. For $r^{100}$ we can use the same argument with $\binom r{101}$, which is a polynomial of degree $101$ in $r$ and positive leading term, to give, for large enough $r$ $$2^r=(1+1)^r\gt\binom r{101}\gt r^{100}$$

The estimates here are very crude indeed, and are not good enough to give transition values for $r$. But they are good enough to furnish a proof of the kind you wanted for the comparison of growth rates.

Answer 2

Let $\lambda > 0$ and consider the limit $$\lim_{x\to\infty} {x^n\over e^{\lambda x}}.$$ This limit can be reduced using L'hospital's rule to $$ \lim_{x\to\infty} {nx^{n-1}\over \lambda e^{\lambda x}}.$$ Repeating, the power whittles away whilst the exponential remains on the bottom.

Answer 3

Solve $2^n > n^{100} \iff n\ln 2>100\ln n\iff \dfrac{n}{\ln n} > \dfrac{100}{\ln 2}$. Let $n = 2^k$, then $ \dfrac{n}{\ln n} = \dfrac{2^k}{k}$,and you solve $2^k > 100k$. Observe the first integer solution $k$ for this is $k = 10$. Thus $n = 2^{10} = 1,024$ .

Answer 4

$$n^{100}=2^n$$ $$100\ln(n)=n\ln(2)$$ $$\frac{\ln(n)}{n}=\frac{\ln(2)}{100}$$ let $n=e^{-x}$ $$xe^{x}=\frac{-\ln(2)}{100}$$ then you can use the Lambert W function $W(x)$ to find the value of $x$, then work backwards to $n$

EDIT: $$x=W\left(\frac{-\ln(2)}{100}\right)$$ $$n=-\ln\left[W\left(\frac{-\ln(2)}{100}\right)\right]$$

Answer 5

If you know that $2^n$ grows faster than $n^{100}$ then you understand that it is a special case of the more general result that exponential functions grow faster than polynomials.

Moreover knowing this fact may mean one has heard or read this somewhere, but in a deeper and crucial sense knowing it means one knows the proof of the following theorem:

Theorem: If $a>1$ then $\lim\limits _{n\to\infty} \dfrac{n^b} {a^n} =0$ for any real number $b$.

The proof is not difficult. Let's choose a positive integer $k$ such that $k>b$ and set $a=1+c$ so that $c>0$. Next using binomial theorem we have $$a^n=(1+c) ^n>\binom {n} {k+1} c^{k+1}$$ if $n>k+1$. Thus we have $$0<\frac{n^b}{a^n}<\dfrac{n^k}{{\displaystyle \binom{n} {k+1}c^{k+1} }}$$ for $n>k+1$. Using Squeeze Theorem it follows that $n^b/a^n\to 0$.

This proves that if $a>1$ then eventually $a^n$ will become far greater than $n^b$ no matter what $b$ is. Finding the first value of $n$ where $a^n>n^b$ requires some numerical analysis based on values of $a, b$.