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

  • Thread starter Thread starter joshanders_84
  • Start date Start date
  • Tags Tags
    Induction Proof
AI Thread Summary
To prove that 2^n < n! for n >= 4 using induction, start with the base case of n = 4, which holds true. The inductive hypothesis assumes that n! > 2^n for n >= 4. To prove the case for n + 1, express (n + 1)! as n! * (n + 1) and apply the inductive hypothesis. By showing that n! * (n + 1) > 2^n * (n + 1) and confirming that n + 1 > 2, you can derive that (n + 1)! > 2^(n + 1). This method effectively demonstrates the inequality holds for all n >= 4.
joshanders_84
Messages
23
Reaction score
0
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
 
Physics news on Phys.org
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.
 
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.
 
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.
 
I saw a great walkthrough of this proof on inductiveproofs.com. It's an e course about how to write inductive proofs. Very helpful!
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top