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!

Inductive proof that (n!)^2 >n^n for n≥3

  1. Sep 4, 2011 #1
    1. The problem statement, all variables and given/known data
    Give an inductive proof that (n!)^2 > n^n for n≥3


    2. Relevant equations



    3. The attempt at a solution
    The case n=3 is easy (3! = 6, 6^2 = 6; 3^3 = 27; 36>27 : QED)

    I can write out/expand ((n+1)!)^2 and (n+1)^(n+1), but I'm lost trying to manipulate the resulting expressions to prove the LHS > RHS.

    Help please.

    (First post here, please be gentle)
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Sep 4, 2011 #2
    You are not using the Inductive method. You must assume that the inequality is true for some [itex]n = k \ge 3[/itex] and then prove its validity for [itex]n = k + 1[/itex] using that assumption.
     
  4. Sep 4, 2011 #3
    For now, I will only give you the hint that the following inequality holds:
    [tex]
    n + 1 > \left(1 + \frac{1}{n}\right)^{\; n} , \; n \ge 2,
    [/tex]
    which is trivial if you know the meaning of the sequence on the right.
     
  5. Sep 4, 2011 #4
    Thanks very much Dickfore!

    It's not that I don't (didn't) know how to do an induction proof, but that I expressed myself wrongly. Also, I see you can use symbols (Latex?), which is good, but I need to learn how myself.

    I'll work on this, with your hint. If I can work it out myself, is it OK to post the solution? Or is it better just that I know, myself, how to do it? Sorry, but I'm new, and I don't know the ropes (but I'm extremely happy to have found this forum!!!!)
     
  6. Sep 4, 2011 #5
    If you're just stuck on the algebra, maybe you could scan your work and post it as an image and we could point you in the right direction?
     
  7. Sep 4, 2011 #6
    If you find the solution, using the hint I gave, would you mind scanning it and attaching it here in case you cannot write it out in LaTeX? After that, we can go on and justify the inequality. I strongly encourage you to try and master LaTeX as it is very useful in communicating mathematical ideas.
     
  8. Sep 4, 2011 #7
    Ditto about latex, but your first post isn't really the time to try it out on a long string of algebra, unless you have a LOT of time... I find it's better to learn starting on single equations.
     
  9. Sep 4, 2011 #8
    (n+1)^(n+1) = (n+1)(n+1)^n - by definition
    = (n+1) ((1+1/n)^n) n^n - because (n+1) = n(1+1/n)
    < (n+1) ((1+1/n)^n) (n!)^2 - per the inductive method
    < (n+1)(n+1) (n!)^2 (n≥2) - per Dickfore's hint
    = ((n+1)^2) (n!)^2
    = ((n+1)!)^2 - by definition

    -> (n+1)^(n+1) < ((n+1)!)^2 QED

    Pretty ugly to read, and incredibly easy to mis-type, but a sound, inductive, proof nonetheless.

    At least I think so.

    Yes, ArcanaNoir, I will be investing the time to learn Latex.

    That leaves just the inequality in Dickfore's post; it's obviously true, and relatively easy to prove, which I've done (but I'll post the proof in a later post, if you guys think it would be good, in terms of my learning this stuff).

    So, a REALLY BIG THANK YOU! :smile:
     
  10. Sep 4, 2011 #9
    Problem statement:
    [tex]
    \left(n!\right)^{\;n} > n^{\;n} , n \ge 3
    [/tex]

    Proof (a couple of lines anyway):

    [tex]
    \left(n + 1\right)^{\;\left(n+1\right)} =\left(n + 1\right) \left(n + 1\right)^{\;n} [/tex] - by definition
    [tex]
    = \left(n + 1\right) n^{\;n} \left(1 + \frac{1}{n}\right)^{\; n} [/tex] - because ...

    OK, so that kinda works, but there are some aspects I don't understand yet ...
     
  11. Sep 4, 2011 #10
    What happened to the factorial?
     
  12. Sep 4, 2011 #11
    He's proving it from the right to the left.
     
  13. Sep 4, 2011 #12
  14. Sep 4, 2011 #13
    Oh dear, is that a mistake? :redface:

    Does it make the proof wrong? :cry:

    I think I could re-write it, going the other way, and maybe even using Latex (though I still haven't got the hang of how to get the number of spaces right, nor the line spacing ...).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Inductive proof that (n!)^2 >n^n for n≥3
Loading...