# 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?

-
Did you try also some other proofs than induction? Or is there some reason why you want to do is this way? My first impules (and several comments bellow suggest the same) would be trying to prove some estimates for some real functions - e.g. by computing derivates and checking their properties. –  Martin Sleziak Jul 7 '11 at 7:14
The reason for a proof by induction is that I had proved the cases k = 1,2,3,4 by induction and so also wanted to prove the general case likewise. –  K4321 Jul 7 '11 at 16:36

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.2^k \ge \left(\frac{k+1}k\right)^2. 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.

-
It might simplify the proof a bit if your Lemma 1) was $2^k \gt k^2 + 1$ for $k \ge 5$, which has a nice combinatorial proof. Consider $\{1, 2, \dots, k\}$. Number of subsets of size $2$ + number of size $k-2$ + number of size $1$ + 1 (empty set) is $k^2+1$. Since we haven't counted subsets of size $k-1$, $2^k \gt k^2 + 1$. –  Aryabhata Jul 7 '11 at 6:46
Proof looks good. It is very natural. The only sense in which it is cumbersome is that it is cumbersome to type! If the rules didn't say induction, one would save a bit of work, but very similar estimates would be needed. –  André Nicolas Jul 7 '11 at 6:47
@user: For the induction step, all we need is that $\frac{x}{\log_2 x}$ is an increasing function. For the base case, by considering something slightly different, we can simplify the whole thing (see my comment above). –  Aryabhata Jul 7 '11 at 6:54
@Aryabhata: If I am not mistaken, the function $\frac{x}{\operatorname{lg}x}$ is increasing only from some point on. So some cases would still have to be verified by another method. (I do not have time to make the calculations right now, but I guess the minimum of this function could be at $x=e$.) –  Martin Sleziak Jul 7 '11 at 7:17
@Martin: Yes, for $x \gt e$. Note that we would take $x$ to be of the form $n^2 + 1$, so the amount of special cases to verify by hand should not be too much. –  Aryabhata Jul 7 '11 at 16:06

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.

-
Perhaps there's some way to avoid the use of analytic arguments ? PS : thanks for the up and the badge ( I'm new here and this is my first post ) :-) –  Bouazza S. Jul 7 '11 at 19:16
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$.