25
$\begingroup$

I'm having difficulty solving an exercise in my course.

The question is:

Prove that $n!\geq 2^n$.

We have to do this by induction. I started like this:

  1. The lowest natural number where the assumption is correct is $4$ as: $4! \geq 2^4 \iff 24 \ge 16$.
  2. The assumption is: $n! \ge 2^n$.

Now proof for $(n+1)$ which brings me to: $(n+1)! \ge 2^{(n+1)}$

I think I can rewrite it somehow like this:

$$ {(n+1)} \times {n!} \stackrel{\text{(definition of factorial)}}{\ge} 2^n \times 2 $$

$$ (n+1) \times 2^n \ge 2^n \times 2 $$

Then I think I can eliminate the $2^n$ and have something like this: $n+1 \ge 2$, or $n \ge 1$.

But I think I'm wrong here some where and was hoping somebody has some advice on this. How can I prove the above assumption?

Any help would be appreciated, kind regards.

$\endgroup$
2
  • $\begingroup$ Looks good to me. More might be said if you wrote why you think you're wrong. $\endgroup$
    – joriki
    Commented Oct 29, 2011 at 16:23
  • $\begingroup$ Well problem is I'm not really experienced with proof by induction. I'm having trouble understanding it. If I end with $n >= 1$, how did I prove that the assumption is correct for every natural number after 4? $\endgroup$ Commented Oct 29, 2011 at 16:25

3 Answers 3

22
$\begingroup$

In the induction step you want to show that if $k!\ge 2^k$ for some $k\ge 4$, then $(k+1)!\ge 2^{k+1}$. Since you already know that $4!\ge 2^4$, the principle of mathematical induction will then allow you to conclude that $n!\ge 2^n$ for all $n\ge 4$. You have all of the necessary pieces; you just need to put them together properly. Specifically, you can argue as follows.

Suppose that $k!\ge 2^k$, where $k\ge 4$; this is your induction hypothesis. Then $$\begin{align*} (k+1)! &= (k+1)k!\text{ (by the definition of factorial)}\\ &\ge (k+1)2^k\text{ (by the induction hypothesis)}\\ &> 2\cdot2^k\text{ (since }k\ge 4\text{)}\\ &= 2^{k+1}. \end{align*}$$ This completes the induction step: it shows that if $k\ge 4$, then $$k!\ge 2^k \implies (k+1)!\ge 2^{k+1}.$$

$\endgroup$
11
  • 1
    $\begingroup$ First of all thanks for your answer. How did you go from $\ge (k+1)2^k$ to $> 2 x 2^k$? $\endgroup$ Commented Oct 29, 2011 at 17:01
  • 1
    $\begingroup$ @Floris: $k+1>2$, so $(k+1)2^k>2\cdot 2^k$. $\endgroup$ Commented Oct 29, 2011 at 17:04
  • $\begingroup$ oh okay I get it, thanks! $\endgroup$ Commented Oct 29, 2011 at 17:42
  • 2
    $\begingroup$ @mp19uy: Certainly: if $X>Y$, then it’s certainly true that $X\ge Y$. $\endgroup$ Commented Jul 30, 2013 at 16:10
  • 2
    $\begingroup$ @mp19uy; Yes, because $X \geq Y \implies X > Y$ or $X = Y$. So if $X>Y$ is true, than $X \geq Y$ must be true, because the OR is satisfied. $\endgroup$
    – Mythio
    Commented Jul 30, 2013 at 19:43
12
$\begingroup$

I am going to provide a different way of going about it--this is essentially Brian M. Scott's proof in reverse. As people have pointed out, if you can show that $n! > 2^n$, then you will have shown that $n! \geq 2^n$ (in this sense, you can think of $>$ as stronger than $\geq$ because $>$ implies $\geq$).

When considering $n! \geq 2^n$ and how you got stuck trying to work from left to right to prove the argument by induction, it may behoove you in some instances to actually work from right to left since $n! \geq 2^n$ is the exact same as $2^n \leq n!$. With this in mind, I will give a small proof that $2^n < n!$ for $n\geq 4$ (like I said, it is very similar to Brian's, but it provides a different way of going about it nonetheless that may be useful for you or others in the future).


For $n\geq 4$, denote the statement involving $n$ by $$ S(n) : 2^n<n!. $$ Base step ($n=4$): Since $2^4=16$ and $4!=24$, the statement $S(4)$ is true.

Inductive step: Fix some $k \geq 4$ and assume that $$ S(k) : 2^k < k! $$ is true. To be shown is that $$ S(k+1) : 2^{k+1} < (k+1)! $$ follows. Beginning with the left side of $S(k+1)$, \begin{align} 2^{k+1} &= 2(2^k)\\[0.5em] &< 2(k!)\tag{by $S(k)$}\\[0.5em] &< (k+1)(k!)\tag{since $k\geq 4$}\\[0.5em] &= (k+1)!, \end{align} the right side of $S(k+1)$. This concludes the inductive step $S(k)\to S(k+1)$.

Thus, by mathematical induction, for all $n\geq 4$, the inequality $S(n)$ is true.

$\endgroup$
1
  • $\begingroup$ Much more comprehensible to me. Thank you. $\endgroup$ Commented Sep 30, 2015 at 19:32
1
$\begingroup$

As with virtually any kind of proof, it is not possible to give step-by step instructions for what to do. The best you can expect is to compile a collection of useful suggestions which may work or may not in any particular instance.

A suggestion in developing induction proofs is: look for the connections between the inductive assumption and the desired conclusion. How can you get from the former to the latter? In this case, your assumption is $$2^k<(k+1)!\ ,$$ and you wish to prove $$2^{k+1}<(k+2)!\ .$$ So: what is the connection between $2^k$ and $2^{k+1}$? What could you do to the assumption to make it look (at least a bit) like the desired conclusion? Could you finish the proof from there?

Alternatively: what is the connection between $(k+1)!$ and $(k+2)!\,$? And then the same questions.

I guess in principle you could also ask: what is the connection between $(k+1)!$ and $2^{k+1}$, but this seems less likely to be successful.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .