Is $2^n$ always dominate $n^k$, where $k$ is some fixed natural number

Question

Is $2^n$ always dominate $n^k$, where $k$ is some fixed natural number.

I have hard time thinking about this? My friend say yes but we are not able to come up with any proper proof and it also feels so counterintuitive. We fixed $k=10$ and tried to put the values of $n$ and $n^{10}$ seems to be increasing way faster than $2^n$.

Can some one give a general argument for this fact?

Answer 1

$2^{n} >n^{k}$ iff $ n \, log \, 2>k\, log \, n$ iff $\frac n {log \, n} >\frac k {\log \, 2}$ which is true for all $n$ sufficiently large because $\frac n {log \, n} \to \infty$ as $ n \to \infty$.

Answer 2

Another way, without using logarithms, is to examine the binomial expansion as follows:

$$2^n=(1+1)^n=\binom n0+\binom n1+\dots +\binom nr+\dots \binom nn$$

The terms on the right certainly include (for $n\gt r+1)$ $$\binom n{r+1}=\frac 1{(r+1)!}\cdot n(n-1)\dots (n-r)$$

This is a polynomial of degree $r+1$ in $n$ with positive leading coefficient, and it is easy to show that this dominates $n^r$ for $n$ large enough using entirely elementary estimates.