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! > 2^n$$
and try to get to
$$(n+1)! > 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!>2^n$$
and
$$n > 4$$

In class the proof might look something like this:
$$(n+1)!=n! (n+1)$$
from the inductive hypothesis we have
$$n! (n+1) > 2^n (n+1)$$
since $$n>1$$ we have
$$2^n(n+1) > 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) > 2^n(n+1) > 2^n(2) =2^{n+1}$$
$$(n+1)! > 2^{n+1}$$

In general, it's worth trying to figure out wether it 'safe'
to multiply
$$n!>2^n$$
by
$$n+1 > 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!