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:
    n + 1 > \left(1 + \frac{1}{n}\right)^{\; n} , \; n \ge 2,
    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:
    \left(n!\right)^{\;n} > n^{\;n} , n \ge 3

    Proof (a couple of lines anyway):

    \left(n + 1\right)^{\;\left(n+1\right)} =\left(n + 1\right) \left(n + 1\right)^{\;n} [/tex] - by definition
    = \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 ...).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook