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)$.
 A: 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$. 
A: Write the inequality as
$n < 2^{n/k}$.
Suppose this is true for $n$.
I want to find conditions such that
this is also true for $n+1$.
By assumption,
$n+1 
= n(1+\frac1{n})
< 2^{n/k}(1+\frac1{n})
$
and this is
less than
$2^{(n+1)/k}$
if
$2^{n/k}(1+\frac1{n})
< 2^{(n+1)/k}$
or
$2^{1/k} > 1+\frac1{n}$.
I showed in another solution
(from $(1+\frac{x}{k})^k < \frac1{1-x}$
for $0 < x < 1$,with $x = \frac12$)
 that
$2^{1/k} > 1+\frac1{2k}$,
so, if $n \ge 2k$
and
$2^n > n^k$,
then
$2^m > m^k$ for
all $m \ge n$.
We now need to find an initial $n \ge 2k$
such that $2^n > n^k$.
Let's try $n = ak$ for some $a$.
$2^{ak} > (ak)^k
\iff 2^a > ak
$.
Almost, but not quite.
Let's try $n = k^2$.
$2^{k^2} > (k^2)^k
\iff 2^{k} > k^2
$.
This is easy by induction.
$2^5 > 5^2$,
and, if $2^k > k^2$ and $k \ge 5$,
$$(k+1)^2 = k^2+2k+1
= k^2(1+\frac{2}{k}+\frac1{k^2})
< 2^k(1+\frac{2}{5}+\frac1{25})
< 2^k(2)
= 2^{k+1}
$$
So, by this nested induction,
if $k \ge 5$,
if $n \ge k^2$
(so that, certainly, $n \ge 2k$),
$2^n > n^k$.
For $k = 2, 3,$ and $4$,
respective values of
$n \ge 2k$ such that
$2^n > n^k$ are
$5$ ($2^5 > 5^2$),
$10$ ($2^{10} > 10^3$),
and
$17$ ($2^{17} = 131072> 17^4=83521$).
These values of $n$ happen to be
$k^2+1$,
so the final result is:
If $n$ and $k$ are integers
and $k \ge 2$
and
$n \ge k^2+1$,
then
$2^n > n^k$.
A: 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 $$
A: Pick $n > 2k$. Then, 
$$
2^n > \binom{n}{k + 1} = \frac{n (n - 1) \cdot \ldots \cdot (n - k)}{(k+1)!}
\geq \frac{n^{k + 1}}{2^{k+1} (k+1)!}
$$ 
by a trivial combinatorial argument for the first inequality, and using $n - k > n/2$ in the second inequality.
Therefore $2^n > n^k$ as soon as
$$
n > 2^{k + 1} (k + 1)!
$$
