# Induction Again

1. Jun 26, 2008

### Moridin

1. The problem statement, all variables and given/known data

Show that

$$\forall n \in \mathbb{N}:~~(n!)^{2} < 2^{n^{2}}$$

3. The attempt at a solution

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

(1!)2 = 1; 21 = 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.

2. Jun 26, 2008

### Defennder

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.

3. Jun 27, 2008

### Moridin

Thanks, I solved it now.