Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

3 Answers

up vote 7 down vote accepted

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.

share|improve this answer
3  
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
1  
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
1  
@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
show 5 more comments

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.

share|improve this answer
1  
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
add comment

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

share|improve this answer
    
Induction also works for the base case. –  André Nicolas Jul 7 '11 at 5:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.