Answer to Question #115558 in Discrete Mathematics for Jeff Kings

Question

Prove that n ! > 2^n for n a positive integer greater than or equal to 4.
Prove that LHS = RHS

Answer 1

We apply the method of mathematical induction.

Induction basis : $n=4$

$$\left\{\begin{array}{l} n!=4!=1\cdot2\cdot3\cdot4=24\\ 2^n=2^4=16 \end{array}\right.\longrightarrow 4!=24>16=2^4$$

Induction assumption : suppose that the inequalities hold for all values $k\le n$

$$k!>2^k, k=\overline{1,\ldots,n}$$

Induction step : need to prove that

$$\left(n+1\right)!>2^{n+1}$$

Proof.

$$\left(n+1\right)!=\left(n!\right)\cdot\left(n+1\right)>2^n\cdot\left(n+1\right)\to\\[0.3cm] \left.2^n\cdot\left(n+1\right)>2^{n+1}\right|\div\left(2^n\right)\\[0.3cm] n+1>2\to\\[0.3cm] n>1-\text{true inequality, since by hypothesis}\,\,\,n>4$$

Q.E.D.