Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Possible Duplicate:
Proof the inequality $n! \geq 2^n$ by induction
Prove by induction that $n!>2^n$ for all integers $n\ge4$.
I know that I have to start from the basic step, which is to confirm the above for $n=4$, being $4!>2^4$, which equals to $24>16$.
How do I continue though. I do not know how to develop the next step.
Thank you.
Suppose that when $n=k$ $(k≥4)$, we have that $k!>2^k$.
Now, we have to prove that $(k+1)!>2^{k+1}$ when $n=(k+1) (k≥4)$.
$(k+1)! = (k+1)k! > (k+1)2^k$ (since $k!>2^k$)
That implies $(k+1)!>2^k \cdot 2$ (since $(k+1)>2$ because of $k$ is greater than or equal to $4$)
Therefore, $(k+1)!>2^{k+1}$
Finally, we may conclude that $n!>2^n$ for all integers $n≥4$
Here's a suggestion. We have that $(n+1)! = (n+1)n!$ and $2^{n+1} = 2\cdot 2^n$. Then, if we know that $n! > 2^n$, and we multiply $n!$ by $n+1$ and $2^n$ by $2$, can you work out what will happen to the inequality?
Guide: If $a>b>0$ and $c>d>0$, then we know that $ac>bd$. Now if we know $n!>2^n$ for some positive integer $n$, and we also know that $n+1>2$....
Hint: prove inductively that a product is $> 1$ if each factor is $>1$. Apply that to the product $$\frac{n!}{2^n}\: =\: \frac{4!}{2^4} \frac{5}2 \frac{6}2 \frac{7}2\: \cdots\:\frac{n}2$$
This is a prototypical example of a proof employing multiplicative telescopy. Notice how much simpler the proof becomes after transforming into a form where the induction is obvious, namely: $\:$ a product is $>1$ if all factors are $>1$. Many inductive proofs reduce to standard inductions.
(i) When $n=4$, we can easily prove that $\frac{4!}{2^{4}}=\frac{24}{16}>1$.
(ii) Suppose that when $n=k$ $(k\geq4)$, we have that $k!>2^{k}$.
(iii) Now, we need to prove when $n=(k+1)$ $(k\geq4)$, we also have $(k+1)!>2^{k+1}$.
We transfer the equation that $\frac{k+1}{2}k!>2^{k}$. As (2), we have known that $k!>2^{k}$, now we only need to prove that $\frac{k+1}{2}>1.0$.
We have known that $k\geq 4$, hence, it easily proves that $\frac{k+1}{2}>1$. In other words, we prove that $(k+1)!>2^{k+1}$.
Thereby, $n!>2^{n}$ for all integers $n\geq 4$. $\square$
