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 Question

  1. Jun 11, 2006 #1
    I have this question in my text that I can not understand

    here it is

    Show that 2^n > n^2 whenever n is an integer > 4.

    the part in the answer that is confusing me is the inductive step

    Here is what the text has for this part of the answer

    Now we assume the induction hypothesis that 2^k > k^2 and want to derive the statment 2^(k+1) > (k+1)^2. Working from the right had side, we have (k+1)^2 = k^2 + 2k + 1 < k^2 + k + 1 = k^2 + 2k + k < k^2 + 3k < K^2 + k^2 (Since k > 3). Thus we have (k+1)^2 < 2k^2 < 2*2^k(by IH) which in turn = 2^(k+1)

    Can someone please explain this to me?? Please

    thanks

    LT
     
    Last edited: Jun 11, 2006
  2. jcsd
  3. Jun 11, 2006 #2

    StatusX

    User Avatar
    Homework Helper

    I think you may have copied that wrong. Check the book again, and try to find the step that's confusing you.
     
  4. Jun 11, 2006 #3
    Thanks. I have updated this statment (k+1)^2 = k^2 + 2k + 1 < k^2 + k + 1 = k^2 + 2k + k < k^2 + 3k < K^2 + k^2 (Since k > 3).

    Sorry.

    This is actually the part that I start to get confused on. (k+1)^2 = k^2 + 2k + 1 < k^2 + k + 1 = k^2 + 2k + k < k^2 + 3k < K^2 + k^2 (Since k > 3).

    I understand this (k+1)^2 = k^2 + 2k + 1 but where does the rest of it come from.

    Thanks
     
  5. Jun 11, 2006 #4
    It makes sense if you just omit the part with [tex]k^2 + k + 1[/tex]. That term does not obey either relation as purported.

    If we ignore that, the rest follow pretty easily.

    [tex](k+1)^2 = k^2 + 2k + 1[/tex] trivially. Since we already know that [tex]1 < k[/tex], we can add [tex]k^2 + 2k[/tex] to both sides to get:
    [tex]k^2 + 2k +1 < k^2 + 2k + k[/tex].

    The second expression here simplfies to [tex]k^2 + 3k[/tex]. And, since we know that [tex]3 < k[/tex], it must follow that [tex]3k < k^2[/tex]. But, then, we see that:
    [tex]k^2 + 3k < k^2 + k^2[/tex].

    The right side of this, then, simplifies to [tex]2k^2[/tex].

    So, this shows that [tex](k+1)^2 < 2k^2[/tex] for all [tex]k[/tex] of interest. The rest you seem to be clear on already.
     
  6. Jun 11, 2006 #5
    Thanks for your response.

    When you say add K^2 + 2k to both side are you added it to 1 < k? How do you know to use 1 < k?

    where does the 3k < k^2 come from?? and where does (k+1)^2 < 2k^2 < 2*2^k come from??
     
  7. Jun 11, 2006 #6
    I used [tex]1 < k[/tex] because that was what made sense based on what you had posted. Overall, this method isn't quite what I would do if posed with the problem.

    [tex]3k < k^2[/tex] comes from multiplying both sides of [tex]3 < k[/tex] by [tex]k[/tex].

    The argument I went through shows that [tex](k+1)^2 < 2k^2[/tex]. The induction hypothesis states that [tex]k^2 < 2^k[/tex]; so, multiplying both sides by two gives the second piece of that last inequality.
     
  8. Jun 11, 2006 #7
    Thanks

    Is there a better or a simplfied way of doing this?
     
  9. Jun 11, 2006 #8

    StatusX

    User Avatar
    Homework Helper

    I don't think there is a much simpler way to do this. The idea is that when k increases by 1, 2^k doubles, so you need to show that k^2 increases by less, ie, (k+1)^2 < 2k^2. Then given that k^2 is initially (ie, at k=5) less than 2^k, this shows it will remain so for all k.
     
  10. Jun 11, 2006 #9
    I would start from the other end.

    [tex]2^{k+1} = 2*2^k > 2k^2[/tex], by the induction hypothesis.

    Then, [tex]2k^2 = (k + (\sqrt{2} - 1)k)^2[\tex].

    This means that [tex]2k^2 > (k + 1)^2[\tex] for all [tex]k[/tex] such that [tex](\sqrt{2} - 1)k > 1[/tex]. This condition becomes [tex]k > \frac{1}{\sqrt{2} - 1} \approx 2.414[/tex]. Since we're only interested in [tex]k > 4[/tex], this shows that [tex]2^{k+1} > (k+1)^2[\tex].
     
  11. Jun 11, 2006 #10
    I would start from the other end.

    [tex]2^{k+1} = 2*2^k > 2k^2[/tex], by the induction hypothesis.

    Then, [tex]2k^2 = (k + (\sqrt{2} - 1)k)^2[/tex].

    This means that [tex]2k^2 > (k + 1)^2[/tex] for all [tex]k[/tex] such that [tex](\sqrt{2} - 1)k > 1[/tex]. This condition becomes [tex]k > \frac{1}{\sqrt{2} - 1} \approx 2.414[/tex]. Since we're only interested in [tex]k > 4[/tex], this shows that [tex]2^{k+1} > (k+1)^2[/tex].
     
    Last edited: Jun 11, 2006
  12. Jun 12, 2006 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I wouldn't start 'from the other end'. Why? Because the exam at the end will want to test the solver's ability to do induction, which is a useful if unenlightening tool.

    In general, you learn from experience. One important lesson to learn, based on the OP's question "How do you know to use 1 < k?", is that when you look at a question you do not always expect to see how to solve it. You must play around with things until you get the right answer. I suppose if you just read the textbook it seems as if the writer instantly knows the correct method to employ. However, that is not how maths works. Dirac (or Feynmann) is supposed to have given a lecture once where he said: thanks for rewarding me with a prize for this clever idea of mine, I'd like to share with you the stupid ideas I went through before I came to this one.

    You just play around with things until you see something that might help. You cannot expect to just write down the answer straight away.
     
  13. Jun 12, 2006 #12
    It's still an inductive proof the way I approached it, since it still relies on the assumption [tex]2^k > k^2[/tex] to show that [tex]2^(k+1) > (k+1)^2[/tex]. I was simply pointing what I find to be a simpler way of proving the inductive step.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof Question
  1. Proof question (Replies: 1)

  2. Proof question (Replies: 2)

  3. A proof question (Replies: 5)

  4. A proof question (Replies: 5)

  5. Proof Question (Replies: 3)

Loading...