What are the steps to prove 2^n < n! using induction?

[joshanders_84]

I'm to prove that for n>=4, 2^n < n! holds, but I don't know where to go after the inductive hypothesis that it holds for n>= 4 after showing it works for the base case (n = 4). Here are my steps so far:

2^(n+1) < (n+1)!
2*(2^n) < (n+1)(n!)

but I dont' know where to now! help is much appreciated, thanks.
Josh

 

[NateTG]

Start with:
1. n \geq 4
2. n! &gt; 2^n
and try to get to
(n+1)! &gt; 2^{n+1}

It shoud be pretty straightforward.

 

[joshanders_84]

I understand that I'm supposed to get there, but I don't see the *proper* first step to take, as the things I have tried haven't gotten me there.

 

[NateTG]

Well, for induction, you usually end up proving the n=1 (or in this case n=4) case first. You've got that done.

Then you need to identify your indictive hypothesis:
e.g.
n!&gt;2^n
and
n &gt; 4

In class the proof might look something like this:
(n+1)!=n! (n+1)
from the inductive hypothesis we have
n! (n+1) &gt; 2^n (n+1)
since n&gt;1 we have
2^n(n+1) &gt; 2^n(2)
and
2^n(2) = 2^{n+1}
Now, we can string it all togther to get the inequality:
(n+1)!=n! (n+1) &gt; 2^n(n+1) &gt; 2^n(2) =2^{n+1}
(n+1)! &gt; 2^{n+1}

In general, it's worth trying to figure out wether it 'safe'
to multiply
n!&gt;2^n
by
n+1 &gt; 2
while preserving the inequality.
Which is really what I wanted to do in my head. As soon as you are sure it is legitemate, you're done.

 

[bryanfoobar]

I saw a great walkthrough of this proof on inductiveproofs.com. It's an e course about how to write inductive proofs. Very helpful!