Prove: (n!)^2 < 2^{n^2} Homework Problem

[Moridin]

Homework Statement

Show that

\forall n \in \mathbb{N}:~~(n!)^{2} &lt; 2^{n^{2}}

The Attempt at a Solution

(1) Show that it is true for n = 1:

(1!)² = 1; 2¹ = 2; => 1 < 2

(2) Show that if it is true for n = p, then it is true for n = p + 1:

Assume that

(p!)^{2} &lt; 2^{p^{2}}

Now,

((p+1)!)^{2} = ((p+1)(p!))^{2} = (p+1)^{2}(p!)^{2}

So if it could be shown that

(p+1)^{2}(p!)^{2} &lt; 2^{(p+1)^{2}}

then (2) has been demonstrated.

2^{(p+1)^{2}} = 2^{p^{2}} \cdot 2^{2p} \cdot 2

Our assumption shows that

(p!)^{2} &lt; 2^{p^{2}}

so I just need to show that the factor (p+1)^{2} is less than the factor 2^{2p} \cdot 2. I'm not sure how to go about doing that.

 

[Defennder]

(p+1)^{2}(p!)^{2} &lt; 2^{(p+1)^{2}}

So you need to show that (p+1)^2 &lt; 2^{2p+1}

Note that this can be reduced to show (p+1)^2 &lt; (2^p)^2 which in turn can be reduced to p+1 &lt; 2^p

This shouldn't be too hard to prove. You could use calculus to prove it for all real values of p, which would in turn hold for positive integers p.

 

[Moridin]

Thanks, I solved it now.