1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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




Loading...
Similar Threads for Proof through Induction Date
Logic behind a proof Yesterday at 6:17 PM
Proof about equality. Sunday at 1:06 PM
Proof of minimum polynomial Apr 12, 2018
Help with Newton root approximation proof Mar 27, 2018
Every normal line to a sphere passes through its centre. Where does this proof end? Apr 24, 2011