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

1. Sep 4, 2011

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

(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. Sep 4, 2011

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

3. Sep 4, 2011

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

4. Sep 4, 2011

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

5. Sep 4, 2011

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

6. Sep 4, 2011

### Dickfore

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.

7. Sep 4, 2011

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

8. Sep 4, 2011

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

9. Sep 4, 2011

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

10. Sep 4, 2011

### ArcanaNoir

What happened to the factorial?

11. Sep 4, 2011

### Dickfore

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

12. Sep 4, 2011

### ArcanaNoir

ooh.

13. Sep 4, 2011

### fanofphysics

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