Proof by induction that $2^n \gt n^k$ How do I prove using induction that if $k$ is a natural number, then $2^n \gt n^k$ for all $n \geq k^2 + 1$, where $n$ is also a natural number? 
 A: If found only this proof, which is rather cumbersome. I hoppe that I did not make mistake there and that someone will come up with a more elegant solution.

Lemma 1: $2^k\ge k^2$ for any $k\ge 4$.
EDIT: In the comments you can find a nice combinatorial argument provided by Aryabhata which works for $k\ge5$.
Proof by induction: $1^\circ$ For $k=4$ the equality holds.
$2^\circ$ Suppose that the lemma holds for $k$. For $k+1$ we get
$2^{k+1}=2\cdot2^k \ge \left(\frac{k+1}k\right)^2\cdot k^2 = (k+1)^2$
(since $\frac{k+1}k =1+\frac1k \le \frac 54 \le \sqrt 2$)
Lemma 2: $\left(1+\frac1{k^2}\right)^k < 2$ for $k\ge 2$.
We know that $\left(1+\frac1{k^2}\right)^{k^2} < 3$ (see here and
here, you can find this in many introductory calculus textbooks) which means that $\left(1+\frac1{k^2}\right)^k < 3^{1/k} \le
2$.

Claim: If $n=k^2+t$ for some positive integer $t$ and $k\ge 2$
then $2^n>n^k$.
Induction on $t$.
$1^\circ$ For $t=1$. If $k\ge 4$ then we have $2^k\ge k^2$
$\Rightarrow$ $2^{k^2}\ge(k^2)^k$. If we multiply this inequality by
$2>\left(\frac{k^2+1}{k^2}\right)^k$, which we know from Lemma 2, we get $2^n>n^k$. For $k=2,3$ we can verify this by hand.
$2^\circ$ Suppose that $n=k^2+t+1$ and the claim holds for $t$, i.e., we have
$$2^{k^2+t}>(k^2+t)^k$$
We also get $\left(\frac{k^2+t+1}{k^2+t}\right)^k = \left(1+\frac1{k^2+t}\right)^k \le
\left(1+\frac1{k^2}\right)^k < 2$.
By multiplying these two inequatities we get
$$2^{k^2+t+1}>(k^2+t+1)^k$$
$$2^n>n^k$$

The only remaining case is $k=1$, in which case the claim $n\ge 2$ $\Rightarrow$ $2^n>n$ can be shown by induction.
A: If you really want to use induction, then you might use this lemma I came up across with by playing a little with your inequality :)
Lemma 1 :
$ \left( 1+\frac{1}{n} \right)^k < 2 $ for $ k \geq 1 $ ( that means $n \geq 2$ )
Proof of Lemma 1 :
By the convexity of $exp$, we know that $1+\frac{1}{n} < e^{\frac{1}{n}}$, and so $ \left( 1+\frac{1}{n} \right)^k < e^{\frac{k}{n}} $.
It suffices then to prove that $ \ln 2 - \frac{k}{n} > 0 $, which is immediate because $\ln 2 - \frac{k}{n} \geq \ln 2 - \frac{\sqrt{n-1}}{n} = \ln2 - \sqrt{\frac{1}{n} - \frac{1}{n^2}}$ and $x \to \frac{1}{x}-\frac{1}{x^2}$ is a decreasing function on $[2,+\infty[$, so $\ln 2 - \sqrt{ \frac{1}{n} - \frac{1}{n^2} } \geq \ln 2 - \frac{1}{2} > 0$, which completes the proof. 
A: First prove it for $n=k^2 + 1$, and then use induction to show that it holds for all further $n$. The base case itself now involves only $k$, and can perhaps be proved by induction on $k$.
