Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Induction Again

  1. Jun 26, 2008 #1
    1. The problem statement, all variables and given/known data

    Show that

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

    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

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


    [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.
  2. jcsd
  3. Jun 26, 2008 #2


    User Avatar
    Homework Helper

    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.
  4. Jun 27, 2008 #3
    Thanks, I solved it now.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook