Proof by induction that $2^n \gt n^k$

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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$.