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