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!

Prove by induction: 2^n >= 11n + 17

  1. Dec 14, 2015 #1
    1. The problem statement, all variables and given/known data

    Prove by mathematical induction: 2^n >= 11n + 17, for n >= 7, and n is an integer.

    2. Relevant equations


    3. The attempt at a solution

    This is my attempt - I want to see if I'm doing this correctly.

    2^n >= 11n + 17, n >= 7

    basis 2^7 >= 77 + 17

    128 >= 94. True.

    Induction Hypothesis:
    Assume true:
    2^k >= 11k + 17

    Must prove:
    2^k+1 >= 11(k+1) + 17

    2^k * 2 >= 2*(11k + 17) <-- By induction hypothesis, just multiplying both sides by 2.
    2^k * 2 >= 22k + 34

    2^k*2 >= 11(k + 1) + 17
    2^k*2 >= 11k + 28

    2^k+1 >= 11k+28, because
    2^k+1 >= 22k + 34, and 11k + 28 will always be a smaller number.
     
  2. jcsd
  3. Dec 14, 2015 #2

    Svein

    User Avatar
    Science Advisor

    Correct up to this point, but then I do not see what you are up to.
     
  4. Dec 14, 2015 #3
    Thanks for the reply,

    I was just expanding out the k+1, so I could say definitively that the expression being multiplied by 2 in the hypothesis is larger 11(k + 1) + 17
     
  5. Dec 14, 2015 #4

    Svein

    User Avatar
    Science Advisor

    It seems to me that you are trying to run the proof backwards at this point. You have shown that

    2k+1≥22k+34

    Just continue with the right hand side...
     
  6. Dec 14, 2015 #5

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, you have the correct argument. I will suggest ways to write it up nicer.

    You need parentheses in the exponents here and below.

    Above, it would be better to start with the left side of what you are to prove$$
    2^{k+1} = 2\cdot 2^k \ge 2(11k+17) = 22k+34 > 11k+28$$which is much more succinct than what you have below.

     
    Last edited: Dec 14, 2015
  7. Dec 14, 2015 #6
    Very helpful, thanks guys!
     
  8. Dec 14, 2015 #7

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You wrote ## 2^k + 1 \geq 11(k+1) + 17##. I assume you mean ##2{k+1} \geq 11(k+1) + 17##, and if so you need to use parentheses, like this: 2^(k+1) >= 11(k+1) + 17. So simple, yet so crucial!
     
  9. Dec 14, 2015 #8

    Mark44

    Staff: Mentor

    In the part, "I assume you mean...", what you really meant was ##2^{k+1} \geq 11(k+1) + 17##
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Prove by induction: 2^n >= 11n + 17
  1. Help with 3x + y = 17 (Replies: 4)

Loading...