How to prove $2^n < n!$ using Mathematical Induction? [duplicate]

Question

Possible Duplicate:
Proof the inequality $n! \geq 2^n$ by induction

I have the following:

Prove that for all $n \in Z^+,\space n > 3 \implies 2^n < n!$

Please provide the steps and, if possible, an explanation.

Best,

Answer 1

1. for $n=4$ it follows $4! > 2^4$

2. suppose $n! > 2^n$

3. we have to prove : $(n+1)! > 2^{n+1}$

Since $n! > 2^n$ if we multiply both sides of this inequality by $(n+1)$ we can write :

$(n+1) \cdot n! > (n+1) \cdot 2^n >2\cdot 2^n =2^{n+1}$

Hence :

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

Q.E.D.

Answer 2

This is a pretty basic induction argument. Before actually going through it in detail, I’d prefer to see you at least take a serious stab at it. Here are some HINTS:

1. Is the statement true for $n=4$? How do you know?

2. Suppose that $n\ge 4$, and it happens that $n$ that $2^n<n!$ for that $n$. By what must you multiply $2^n$ to get $2^{n+1}$? By what must you multiply $n!$ to get $(n+1)!$? How do these two multipliers compare?

3. If $0<a<b$ and $0<c<d$, how do the numbers $ac$ and $bd$ compare in size?

Answer 3

This question is a duplicate but I'll provide the general case so I can link to it in the future...

---

Lemma 1: Suppose $\rm a,b,c,d>0$. Then we can combine two inequalities into a third:

$$\begin{array}{cc} & \rm a>c~~ \\ & \rm b>d~ \\ \hline\implies & \rm ab>c\,d. \end{array} \qquad$$

Lemma 2: If $\rm r_n>s_n>0$ for $\rm n=1,2,\cdots,N$ then $\rm r_1r_2\cdots r_N> s_1s_2\cdots s_N$.

Proof. The base case $\rm r_1>s_1$ is true by hypothesis. Now suppose that it holds for $\rm N-1$ (inductive hypothesis). Apply lemma $1$ using $\rm a:=r_1r_2\cdots r_{N-1}>c:=s_1s_2\cdots s_{N-1}$ and $\rm b:=r_N>d:=s_N$.

Theorem: Suppose $\rm x_1>y_1>0$ and $\rm \large \frac{x_{n+1}}{x_n}>\frac{y_{n+1}}{y_n}>0$ for each $\rm n\in\mathbb{N}$. Then $\rm x_n> y_n$ for all $\rm n\ge1$.

Proof. Invoke lemma $2$ with $\rm r_n := \large \frac{x_{n+1}}{x_n}$ and $\rm s_n := \frac{y_{n+1}}{y_n}$ to obtain $\rm \large \frac{x_n}{x_1}>\frac{y_n}{y_1}$. Combine with $\rm x_1>y_1$.

---

Applicability: Theorem with $\rm x_n:=n!, ~ y_n:=2^n, ~ \large \frac{x_{n+1}}{x_n} \normalsize =n+1>2= \large \frac{y_{n+1}}{y_n}$ starting at $\rm n=4$.