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

[fanofphysics]

Homework Statement

Give an inductive proof that (n!)^2 > n^n for n≥3

Homework Equations

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)

 

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

 

[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?

Does it make the proof wrong?

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