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: Proof through Induction with Inequality

  1. Oct 23, 2007 #1
    1. The problem statement, all variables and given/known data


    Original Problem Text:
    http://img264.imageshack.us/img264/5882/problem3pn7.th.gif [Broken]

    Prove that, if n [tex]\in[/tex] [tex]N[/tex] and n [tex]\geq[/tex] 2, then 2^(n^2) > n^(n).

    2. Relevant equations

    Some Hints:
    *** (n-1)^(n-1) * 2^(n-1) = (2n - 2)^(n-1)
    *** If n >= 2 then (2n - 2) >= n.
    *** If n >= 1 then 2^(n) >= n.

    3. The attempt at a solution

    Using Induction:

    For the base step, suppose that n = 2. This implies that 2^(2^2) = 16, and 2^(2)= 4, and 16 > 4, so the base step is proven true.
    Suppose that n>2, and that the theorem has been proven for all smaller values of n.

    Then we compute:
    2^(n^2) > n^n
    2^(n-1)^2 > (n-1)^(n-1)
    ***Multiply both sides by 2^(n-1)***
    2^(n-1)^2 * 2^(n-1) > (n-1)^(n-1) * 2^(n-1)
    2^(n-1)^2 * 2^(n-1) = 2^(n^2 - n) = 2^(n(n-1))
    2^(n(n-1)) > (2n -2)^(n-1)
    ***Now here's the screwy part - I took the (n-1) root across the inequality. I have my doubts about the mathematical legality of such an operation. ***
    2^(n) > 2n - 2
    2n -2 [tex]\geq[/tex] n (since n [tex]\geq[/tex] 2)
    2^(n) > n
    2^(n^2) > n^(2)


    Does this proof make any sense at all? Does it even remotely resemble a proof? I should point out that I'm using (n-1) in place of (n+1) because that's the way my professor did it.

    Thanks a lot for any help!
     
    Last edited by a moderator: May 3, 2017
  2. jcsd
  3. Oct 23, 2007 #2

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    I'd try to use all hints they gave; they are usually given for a reason.
     
  4. Oct 23, 2007 #3
    I believe I used just about all the hints my professor gave. Though whether I used them correctly is questionable.

    For the first hint I multiplied both sides by 2^(n-1) in order to fit the form he gave -- i.e.
    2^(n-1)^2 * 2^(n-1) > (n-1)^(n-1) * 2^(n-1)

    For the second hint, I got rid of the (n-1) power on both sides (which itself is a questionable move), which gave the form:
    2^(n) > 2n - 2

    And finally, for the third hint, I related 2n - 2 > n to 2^(n) > 2n -2 > n.

    Thanks again.
     
  5. Oct 24, 2007 #4

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    You are starting with the correct premise but not ending up with 2^(n^2) > n^(n)
     
  6. Oct 24, 2007 #5
    It seems that we can do this without induction, using only the third hint since ...

    [tex]2^{n^2} = 2^{n\times n} = (2^n)^n[/tex]

    It also seems to work for the case [itex]n = 1[/itex]
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook