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

[Moridin]

Homework Statement

Show that

$$\forall n \in \mathbb{N}:~~(n!)^{2} < 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} < 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} < 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} < 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} < 2^{(p+1)^{2}}$$

So you need to show that $$(p+1)^2 < 2^{2p+1}$$

Note that this can be reduced to show $$(p+1)^2 < (2^p)^2$$ which in turn can be reduced to $$p+1 < 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.