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,
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Hint $\rm\displaystyle\ \frac{n!}{2^n}\ =\ \left[\frac{1}2\ \frac{2}{2}\ \frac{3}2\ \frac{4}2\right]\ \frac{5}2\: \frac{6}2\ \cdots\ \frac{n}2_{\phantom{{\frac{I}{I}}\!\!\!\!\!\!}}\ > 1\ $ since each factor is. This is a prototypical proof by multiplicative telescopy. $\endgroup$– Bill DubuqueApr 4, 2012 at 18:10
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
for $n=4$ it follows $4! > 2^4$
suppose $n! > 2^n$
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.
$\begingroup$
$\endgroup$
0
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:
Is the statement true for $n=4$? How do you know?
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?
If $0<a<b$ and $0<c<d$, how do the numbers $ac$ and $bd$ compare in size?
answered Apr 4, 2012 at 7:21
$\begingroup$
$\endgroup$
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$.
