• Support PF! Buy your school textbooks, materials and every day products Here!

Induction Again

  • Thread starter Moridin
  • Start date
  • #1
664
3

Homework Statement



Show that

[tex]\forall n \in \mathbb{N}:~~(n!)^{2} < 2^{n^{2}}[/tex]

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

[tex](p!)^{2} < 2^{p^{2}}[/tex]

Now,

[tex]((p+1)!)^{2} = ((p+1)(p!))^{2} = (p+1)^{2}(p!)^{2}[/tex]

So if it could be shown that

[tex](p+1)^{2}(p!)^{2} < 2^{(p+1)^{2}}[/tex]

then (2) has been demonstrated.

[tex]2^{(p+1)^{2}} = 2^{p^{2}} \cdot 2^{2p} \cdot 2[/tex]

Our assumption shows that

[tex](p!)^{2} < 2^{p^{2}}[/tex]

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

Answers and Replies

  • #2
Defennder
Homework Helper
2,591
5
[tex](p+1)^{2}(p!)^{2} < 2^{(p+1)^{2}}[/tex]
So you need to show that [tex](p+1)^2 < 2^{2p+1}[/tex]

Note that this can be reduced to show [tex] (p+1)^2 < (2^p)^2 [/tex] which in turn can be reduced to [tex]p+1 < 2^p [/tex]

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
664
3
Thanks, I solved it now.
 

Related Threads for: Induction Again

  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
837
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
5
Views
2K
Top