<s>[INST] 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)$.
 [/INST] 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$.
</s>