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

[fanofphysics]

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

[Dickfore]

You are not using the Inductive method. You must assume that the inequality is true for some n = k \ge 3 and then prove its validity for n = k + 1 using that assumption.

[Dickfore]

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.

[fanofphysics]

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!!!!)

[ArcanaNoir]

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?

[Dickfore]

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!!!!)

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.

[ArcanaNoir]

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.

[fanofphysics]

(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:

[fanofphysics]

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} - by definition

= \left(n + 1\right) n^{\;n} \left(1 + \frac{1}{n}\right)^{\; n} - because ...

OK, so that kinda works, but there are some aspects I don't understand yet ...

[ArcanaNoir]

What happened to the factorial?

[Dickfore]

He's proving it from the right to the left.

[ArcanaNoir]

ooh.

[fanofphysics]

He's proving it from the right to the left.
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 ...).