Prove $2^n > n^k$ for all $n \geq k^2 + 1$ I've managed to prove this for a few specific cases of $k$ (($k=3$, $n \geq 10$) and ($k=4$, $n \geq 17$)) with induction, but I just don't see how to generalize it for any $k$. Even double induction is proving difficult because I can't even seem to prove the base case.
Any help is appreciated.
 A: Note the inequality is trivial for $k=0$ so let's consider only $k>0$.
The base case is, of course, establishing $2^{k^2+1} \geq (k^2+1)^k$ for all $k$.
So it suffices to establish
$$\frac{2^{(k+1)^2+1}}{2^{k^2+1}}\geq \frac{(k^2+2k+2)^{k+1}}{(k^2+1)^k}$$
for large enough $k$ and work the finite number of cases left explicitly. So we want to show
$$
2^{2k+1}\geq\left(1+\dfrac{2k+1}{k^2+1}\right)^k (k^2+2k+2)
$$
and since $RHS<\left(1+\dfrac{3k}{k^2}\right)^k(5k^2)<5e^3k^2<135k^2$ it suffices to show
$$
2^{2k+1}\geq 135k^2
$$
which holds for $k\geq 6$.  The cases $k=1,\dots,6$ are easily checked.
Now having got that base case, for the induction step we want
$$
2\geq\left(\frac{n+1}{n}\right)^k
$$
for $n\geq k^2+1$, so it suffices to show
$$
2\geq\left(1+\frac{1}{k^2+1}\right)^k.
$$
This is clearly true when you binomially expand RHS and use the (rather crude) bound $\binom{k}{r}(k^2+1)^{-r}\leq k^{-r}$.
A: Consider this function:
$$
f(u)=u\log 2-k\log u,\quad f'(u)=\log 2-\frac{k}{u}.
$$
If $u\geq \frac{k}{\log 2}$, then $f(u)$ is increasing. Since $k^2+1\geq 2k>\frac{k}{\log 2}$, for all $n\geq k^2+1$ we have:
$$
f(n)\geq f(k^2+1).
$$
Therefore if we prove that $f(k^2+1)>0$ the result is proved. Therefore we should prove only that 
$$
2^{k^2+1}>(k^2+1)^k\implies 2^{k+\frac 1k}>k^2+1 \tag{1}.
$$
But for $k\geq 5$, we have:
$$
2^k=(1+1)^k\geq \binom{k}0+\binom{k}1+\binom{k}2+\binom{k}{k-2}+\binom{k}{k-1}+\binom{k}{k}=k^2+k+2.
$$
Since $2^{1/k}>1$, we have for $k\geq 5$:
$$
2^{k+\frac 1k}\geq k^2+k+2>k^2+1.
$$
The proof follows by checking the inequality $(1)$ for $k=1,2,3,4$.
A: Since you have proven the inequality for $k=3$ and $k=4$, and the cases $k=1$ and $k=2$ are easy, I shall deal with the remaining cases, namely, when $k\geq5$ is an integer.  We shall assume that $k\geq 5$ unless otherwise stated.
First, it can be easily proven by induction that $$2^m>m^2$$ for all integers $m\geq 5$.  Thus, we get
$$2^{k^2}=\left(2^k\right)^k>\left(k^2\right)^k\,.$$
That is, $2^n>n^k$ when $n=k^2$.  This provides the basis step for our proof of the inequality 
$$2^n>n^k\text{ for every integer }n\geq k^2\,.$$
For the inductive step, suppose that $n\geq k^2$ and $2^n>n^k$.  Then,
$$2^{n+1}>2\,n^k>(n+1)^k\,,$$
as
$$\left(1+\frac{1}{n}\right)^k\leq \left(1+\frac{1}{k^2}\right)^k<\text{e}^{\frac{1}{k}}\leq \text{e}^{\frac{1}{5}}<2\,.$$
Here, $\text{e}\approx 2.718$ is the natural base of logarithm, and the famous inequality
$$\left(1+\frac{1}{m}\right)^m<\text{e}\text{ for each positive integer }m$$
has been used.
Indeed, it follows that, for any nonnegative integer $k$ and for any integer $n\geq k^2$ with a single exception when $(k,n)=(3,9)$, we have
$$2^n\geq n^k\,.$$
The inequality becomes an equality if and only if $(k,n)=(0,0)$, $(k,n)=(2,4)$, and $(k,n)=(4,16)$.  Here, we use the convention that $0^0=1$.  In fact, we can find a more appropriate lower bound than $n\geq k^2$.  Let $W_s$ denote the $s$-th branch of the Lambert $W$-function.  Then, for each integer $k\geq 2$, we have
$$2^n\geq n^k\text{ for every integer }n\geq \left\lceil -\frac{k\,W_{-1}\left(-\frac{\ln(2)}{k}\right)}{\ln(2)}\right\rceil=:b_k\,.$$
We have $b_2=4$, $b_3=10$, $b_4=16$, $b_5=23$, and $b_6=30$.  (We can additionally define $b_0:=0$ and $b_1:=0$.)  Because $$W_{-1}(-\epsilon)\approx\ln(\epsilon)$$ for small $\epsilon>0$, we get that $$b_k\approx \frac{k\,\ln\left(\frac{k}{\ln(2)}\right)}{\ln(2)}\approx \frac{k\,\ln(k)}{\ln(2)}$$
for large values of $k$.
