1. Not finding help here? Sign up for a free 30min 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!

Proof through Induction with Inequality

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


    Original Problem Text:
    [​IMG]

    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!
     
  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]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof through Induction with Inequality
Loading...