1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof by Induction: 2^n < n!

  1. Jan 11, 2005 #1
    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
     
  2. jcsd
  3. Jan 11, 2005 #2

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Start with:
    1. [tex]n \geq 4[/tex]
    2. [tex]n! > 2^n[/tex]
    and try to get to
    [tex](n+1)! > 2^{n+1}[/tex]

    It shoud be pretty straightforward.
     
  4. Jan 11, 2005 #3
    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.
     
  5. Jan 11, 2005 #4

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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.
    [tex]n!>2^n[/tex]
    and
    [tex]n > 4[/tex]

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

    In general, it's worth trying to figure out wether it 'safe'
    to multiply
    [tex]n!>2^n[/tex]
    by
    [tex]n+1 > 2 [/tex]
    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.
     
  6. Feb 6, 2012 #5
    I saw a great walkthrough of this proof on inductiveproofs.com. It's an e course about how to write inductive proofs. Very helpful!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof by Induction: 2^n < n!
  1. Proof for n (Replies: 5)

Loading...