# proving $n!>2^n\;\;\forall \;n≥4\;$ by mathematical induction

My teacher proved the following $n!>2^n\;\;\;\forall \;n≥4\;$ in the following way

Basis step: $\;\;4!=24>16$ ok

Induction hypothesis: $\;\;k!>2^k$

Induction step: $\qquad\qquad(k+1)!=k!(k+1)>(k+1)2^k>2^k\cdot 2=2^{k+1}$

I wonder how did he assume that $2^k(k+1)>2^{k}\cdot 2\quad\forall k≥4$?

Don't we have to show it by induction too?

-
If $k\ge 4$, then $k+1> 2$. I guess you could show this by induction, but that seems a bit unnecessary. –  Jared May 20 '13 at 18:02
@Jared you are absolutely right –  iostream007 May 20 '13 at 18:05

We need only take advantage of the proof's hypothesis, when we assume from the start that $k \geq 4$, so those are the only values of $k$ that need to be considered. Clearly, $$\forall\;k\geq 4 \implies k + 1 \geq 4 + 1 = 5 > 2$$

This is where we get that $$2^k \cdot \underbrace{(k + 1)}_{\large > 2} \;\gt \; 2^k \cdot 2 = 2^{k+1},\quad\text{as desired}.$$

-
Getting your proofs on! :-) +1 –  Amzoti May 21 '13 at 0:37

If $k \geq 4$, it follows that $k + 1 \geq 5 > 2$. Hence it is safe to say that $2^k * (k + 1) > 2^k * 2$.

-

You assume by induction hypothesis that $k!>2^k$. Also, you have $k\ge 4$, hence surely $k+1>2$. Multiplying $k+1> 2$ with the positive number $2^k$, you find $(k+1)2^k>2^{k+1}$. And multiplying $k!>2^k$ with the positive number $k+1$ you find $(k+1)!>(k+1)2^k$, whence together the claim $(k+1)!>2^{k+1}$.

-
The question was not to explain the whole proof. Also, the assumption is not that $k! > 2$, but that $k! > 2^k$. –  timvermeulen May 20 '13 at 18:08
Thx, Typo removed –  Hagen von Eitzen May 20 '13 at 18:19