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: Math induction

  1. Jan 26, 2010 #1
    I have to prove by induction that for n>= 4 that 2^n > n^2.

    So i start with the base case and I get 16 >= 16 which is true.
    Then I assume for k that 2^k >= k^2 for k.
    Now I have to that 2^(k+1) >= (k+1)^2

    Now going back to 2^k >= k^2 if I multiply both sides by 2 I get
    2*2^k >= 2*k^2
    2^(k+1) >= 2*k^2

    and from here I get stuck. Any help would be appreciated. Thanks.
  2. jcsd
  3. Jan 26, 2010 #2


    User Avatar
    Science Advisor
    Homework Helper

    4k^2 >= 2k^2
  4. Jan 26, 2010 #3
    I'm sorry but I don't know what you mean by that.
  5. Jan 27, 2010 #4


    User Avatar
    Homework Helper

    It works for the basis of induction, n = 4. Assume it works for some k, so 2^k >= k^2. Then, for k+1, you have 2^(k+1) = 2*2^k >= 2*k^2. Now, can you show that 2*k^2 >= (k+1)^2, for n >= 4?
  6. Jan 27, 2010 #5
    Okay I see why you do that so I guess I have to prove 2*k^2 >= (k+1)^2 by induction.

    When n = 4 we have
    2*(4)^2 = 32
    (4+1)^2 = 25
    So 32 > 25 which is true.

    Then we assume it is true for all n right and now I have to show that
    2*(k+1)^2 >= ((k+1)+1)^2
    which is the same thing as
    2*(k+1)^2 >= (k+2)^2

    Okay now I'm stuck again.
  7. Jan 27, 2010 #6


    User Avatar
    Homework Helper

    So you're trying to prove [itex]2k^2\geq (k+1)^2[/itex] for [itex]k \geq 4[/itex]
    Expanding gives: [itex]2k^2\geq k^2+2k+1[/itex]
    and now collecting like terms: [itex]k^2-2k-1\geq 0[/itex]

    Can you finish this off?
  8. Jan 27, 2010 #7
    No not really. I'm not even sure I'm going the right way because my professor was telling me that I will eventually have to prove another property which is n^2 >= 2n+1 for n>=3. Thanks.
  9. Jan 27, 2010 #8


    User Avatar
    Homework Helper

    That's exactly where you're heading! :tongue:

    I just asked you to prove [itex]k^2-2k-1\geq 0[/itex] for [itex]k\geq 4[/itex] which is basically the same as what your professor said you'll have to do.

    Make the above inequality a perfect square.
  10. Jan 27, 2010 #9
    Okay so from k^2 - 2k - 1 >= 0 for k>= 4 we can rewrite it as

    (k-1)^2 >= 0 for k>= 4. Yes I'm sorry but I still don't see it.
  11. Jan 27, 2010 #10


    User Avatar
    Homework Helper

    No that's not exactly right.
    [itex](k-1)^2=k^2-2k+1[/itex] and you have [itex]k^2-2k-1[/itex]

    What you're actually looking for is [itex](k-1)^2-2\geq 0[/itex]. So, for what positive k is [itex](k-1)^2\geq 2[/itex] ?
  12. Jan 27, 2010 #11
    It is 3 because (3-1)^2 >= 2 because 2^2 >= 2 which is 4 >= 2 but what does that prove then?
  13. Jan 27, 2010 #12


    User Avatar
    Homework Helper

    Yes that's right.

    Well if we backtrack your steps, notice that we were trying to prove [itex]2^k\geq k^2[/itex] o:) Our first step was to show for a base case, and while n=1 and n=2 worked, n=3 is untrue so we started at the first case of n=4.
    Now in the 3rd step you've proven that [itex]2^{k+1}\geq (k+1)^2[/itex] by assuming [itex]2^k\geq k^2[/itex] in your 2nd step and then substituting this assumed result to obtain [itex]2k^2\geq (k+1)^2[/itex].

    That is, if [itex]2^k\geq k^2[/itex] then [itex]2^{k+1}\geq 2k^2[/itex] and surely if we're trying to prove [itex]2^{k+1}\geq (k+1)^2[/itex] then we can substitute [itex]2^{k+1}=2k^2[/itex].

    Now you've shown by logic that for [itex]k\geq 3[/itex], [itex](k-1)^2\geq 2[/itex] which, after giving a little word about how mathematical induction works, you've essentially proven the question for [itex]k\geq 4[/itex]
  14. Jan 27, 2010 #13
    Okay I kind of get. By showing that for k>=3 we know (k-1)^2 >= 2 which originally means 2k^2 >= (k+1)^2 for k>=4 but by proving the first inequality we have proved the previous inequality and thus by proving the previous inequality this means we have proved 2^k >= k^2 for k >= 4. Am I right?
  15. Jan 27, 2010 #14


    User Avatar
    Homework Helper

    Yes, exactly! :approve:
  16. Jan 27, 2010 #15
    Cool, Thanks! :D
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook