Prove that $n^k < 2^n$ for all large enough $n$

If $k\ge 2$ is an integer, prove by elementary means (no calculus or limits) that there is a $N(k)$ such that $n^k < 2^n$ for all integers $n \ge N(k)$. Give an explicit form for $N(k)$.

Note that a polynomial with positive leading coefficient is eventually positive: If $$p(x)=a_0+\dots+a_nx^n$$ and $a_n>0$, then $p(x)>0$ for $x$ large enough. For example, we can write $p(x)=a_n[(c_0+\dots+c_{n-1}x^{n-1})+x^n]$, and note that $$ |c_0+\dots+c_{n-1}x^{n-1}|\le |c_0|+\dots+|c_{n-1}|x^{n-1}\le x^n/2 $$ as long as $K:=\max\{1,2n|c_i|\colon i<n\}<x$, so $\displaystyle |c_i|<\frac{x}{2n}$ for all $i$, and $x^k<x^n$ for all $k<n$. This means that $$ |p(x)|\ge a_n(x^n-|c_0+\dots+c_{n-1}x^{n-1}|)\ge a_n(x^n-x^n/2)>0, $$ the inequality holding at least for $x>K$.

Now, for $n>0$, we have that $\displaystyle 2^n\ge\binom n{k+1}$ (since the left hand side counts all subsets of a set of $n$ elements, and the right hand side only counts those subsets of size exactly $k+1$), and the latter is a polynomial of degree $k+1$ and positive leading coefficient. This means (by the previous paragraph) that $\displaystyle \binom n{k+1}>n^k$ for $n$ large enough, as $\displaystyle \binom n{k+1}-n^k$ is a polynomial with positive leading coefficient. But then $2^n>n^k$, as we wanted.

The value of $K$ can be computed directly from the expansion of $\displaystyle \binom n{k+1}-n^k$.

By Bernoulli

$$\sqrt[2k]{2}^n \geq 1+n(\sqrt[2k]{2}-1) \,.$$

Pick an $N(K)$ so that

$$\sqrt{N(K)}(\sqrt[2k]{2}-1) > 1 \,.(*)$$

Then, for all $n > N(K)$ we have

$$\sqrt[2k]{2}^n \geq 1+n(\sqrt[2k]{2}-1) > \sqrt{n}\sqrt{N(K)}(\sqrt[2k]{2}-1) > \sqrt{n} \,.$$

The value we get for $N(K)$ from $(*)$ is:

$$N(K)=1+\left\lfloor \left( \frac{1}{\sqrt[2k]{2}-1} \right)^2 \right\rfloor $$