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


    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


    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:
    [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]
    [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+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!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook