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!

Is this a valid proof for n! >2^n for all n>3

  1. Sep 25, 2016 #1
    1. The problem statement, all variables and given/known data
    Show that n!>2n for all n>3.

    2. Relevant equations
    I will attempt to use induction.

    3. The attempt at a solution
    We want to show that n!>2n for all n>3.
    Consider the case when n=4.
    [tex] 4! = 24 > 2^4 =16.[/tex]

    We want to show by way of induction that if the inequality is true for some k greater than 4, it is true for k+1.

    Assume the inequality holds for k>4. Then,
    [tex] 2^k < k! [/tex]
    [tex] 2*2^k < 2k![/tex]
    [tex]2^{k+1} < 2k![/tex]
    for k>4.

    But 2k! < (k+1)! for all k>4. Therefore

    [tex]2^{k+1} < (k+1)![/tex]

    and so by induction it follows that n! > 2n for all n > 3.
     
  2. jcsd
  3. Sep 25, 2016 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Proof is ok, but I'm going to be annoying:

    Why?

    Why?

    Why?
     
  4. Sep 25, 2016 #3
    Thank you. That always helps.


    The reason I assumed it held for k>4: 4 is the very first integer greater than 3. I figured if I can establish by induction that it holds for 4, then 5, 6, 7,...k, k+1,... then it must hold for all numbers greater than 3. There is no upper bound on k. I did spin my wheels a bit at first since I'm used to the base case being k=1.

    As for the second part, I multiplied by 2 because that would allow me to easily get the k+1 case because the base for the power is 2, and xax = xa+1. (also I don't believe the way everything relates to the number 2 here is coincidental. I think there might be a deeper relation between the base of the power and when it is larger than the factorial).

    Because I multiplied both sides by a positive integer, so the inequality should remain. The multiplication was done so I can get the k+1 case for the exponent. I then kind of lucked into the next part. I knew I had to get to some point where the left was less than the target quantity, and this worked out well.

    Because:
    [tex]\lim_{n\rightarrow ∞ } \frac{2n!}{(n+1)!} = 0 [/tex]
    *EDIT I had n approaching zero for some reason

    and as for k =3,2,1 and 0, I manually tested them. k>4 is overkill for this part. But I figured that in order remain consistent I'd stick with k >4, since it is necessary for comparing the exponential to the factorial.
     
    Last edited: Sep 25, 2016
  5. Sep 25, 2016 #4

    Math_QED

    User Avatar
    Homework Helper

    This is wrong.
     
  6. Sep 25, 2016 #5

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    There is, however, a small but significant error in your original proof. This is not related to insufficient justification, but is a genuine flaw.

    Big hint: what happened to the case ##n = 5##? Where did you cover that?
     
  7. Sep 25, 2016 #6
    I wrote it wrong. It's supposed to be as n approaches infinity.
     
  8. Sep 25, 2016 #7

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    That means that for all ##\varepsilon>0##, there is an ##N## such that if ##n>N## we have ##2n! <\varepsilon (n+1)!##.

    Your claim is that for all ##n>3## we have ##2n!<(n+1)!##. Those are very distinct statements.
     
  9. Sep 25, 2016 #8
    Oh I see what you're saying.

    For that part when I answered your why question by posting the limit I just meant that because I knew that limit was zero it led me to the idea of trying to set up an inequality where

    2k+1 < 2k! < (k+1)! for k>4.

    I did not actually give a mathematical reason haha. I will think on it and try to articulate a better one.
     
  10. Sep 25, 2016 #9

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    If you mean ##2 \times 2^k < (2k)! ## then that does not follow from the previous line. If you mean ##2 \times 2^k < 2 \times k!## then that does follow.
     
  11. Sep 25, 2016 #10

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    @Battlemage!

    PeroK's question has been ignored. It raises an important point!
     
    Last edited: Sep 25, 2016
  12. Sep 26, 2016 #11
    Yes that's what I meant. I figured a factorial was only grouped with other terms if there were parentheses, but then again it's not like a factorial is in PEMDAS so I would be ignorant of such rules.



    I post these questions at work and unfortunately ran out of time. I was thinking about it, though. Sadly I'm at a loss. More information below...

    Okay... let me see...

    I have manually tested 5 and it works. 5! = 120 >25 = 32.
    Likewise with my last step, 25 = 32 < 2(5!) = 240 < (5+1)! = 6! = 720.

    As for the induction process, I've never done it where the base case wasn't one. Did I do it wrong with my base case of 4?


    Since I included k greater than 4, doesn't that already include 5. I don't quite understand what you're getting at. Any other hints? :/




    EDIT- since we're here, I did find a different way to do it working the other way.

    [tex](k +1)! = (k + 1)k! > (k + 1)2^k[/tex]
    and since k > 4 then
    [tex](k + 1)! > 2^k * 2 [/tex]
    [tex](k + 1)! > 2^{k+1}[/tex]
     
  13. Sep 26, 2016 #12

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    What you did was:

    a) Showed it was true for ##n = 4##

    b) Showed that if it was true for ##k > 4## it was true for ##k+1##

    But, ##k > 4## starts at ##k =5##. So, you didn't cover the step ##P(k = 4) \ \Rightarrow \ \ P(k = 5)##.

    The inductive stage of your proof should have been for ##k \ge 4##.

    On the other issues, I think you have let the questions confuse you and over-elaborated your answers. Your proof depended only on (if ##a, b## are positive):

    ##a < b \ \Rightarrow \ 2a < 2b##

    And

    ##k > 2 \ \Rightarrow \ 2a < ka##

    You must see this, but recognising these simple facts and stating them simply and mathematically is something that generally does not seem to come naturally to many people.

    On a final point, I would tend to write either ##2(k!)## or ##(2k)!## to avoid any ambiguity. Like you, I don't know what PEMDAS has to say about factorials.
     
  14. Sep 26, 2016 #13
    So essentially if I replace the > with a ≥ that would fix the issue?

    So I could have omitted this part?

    Yeah I think I'll do that from now on.

    I appreciate the help by the way.
     
  15. Sep 26, 2016 #14

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, but you should see that yourself.

    There was nothing you could have omitted. You just needed to justify what you were doing a little more.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Is this a valid proof for n! >2^n for all n>3
  1. Prove n^3 <= 2^n (Replies: 9)

Loading...