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?
Proof by induction that $2^n \gt n^k$
-
0The 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. – 2011-07-07
3 Answers
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.
-
0Just came across this in my studies. Nice answer. – 2013-04-26
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.
-
1Perhaps 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 ) :-) – 2011-07-07
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$.
-
0Induction also works for the base case. – 2011-07-07