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!

Mathematical Induction

  1. Jul 11, 2014 #1

    Maylis

    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
    Hello, I am working on the problem in the attached image regarding induction based on the inequality

    [tex]2^n \geq n + 1[/tex]

    I am confused how to do this by proving that if it is assumed to be true for ## n = k ##, then how it is true for ##n = k + 1##. The way I see it, you would just do ## 2^{k+1} \geq (k+1) + 1##. The answer is ##2(k+1) \geq k + 2##, but I do not understand it.
     

    Attached Files:

    Last edited: Jul 11, 2014
  2. jcsd
  3. Jul 11, 2014 #2
    Hello, for inline latex ##\#\### before and after the expression.
    'You would just do' : not exactly, it is what you have to prove assuming ##2^k \geq k+1## holds.
     
  4. Jul 11, 2014 #3
    Hint:
    Let ##a,b,c,d## be four positive numbers such that ##a\gt b## and ##c\gt d##, then we have: $$ac\gt bd.$$ For your particular example you have ##2^{k}\geqslant k+1## and you need to find a relation ##c\gt d## such that when you apply the above rule you get $$2^{k+1}\geqslant (k+1)+1.$$ Can you find such relation and prove it?
     
  5. Jul 11, 2014 #4

    Maylis

    User Avatar
    Gold Member

    So are you saying in this case for ##a > b##, then ## a = 2^k## and ##b = k+1##. Then I need a ##c## and ##d##. Well, I think ## c## would be equal to ##2##, but I need something such that ##d*(k+1) = k + 2##.

    Hence
    [tex] d = k+2/k+1 [/tex]

    Then it follows
    [tex] ac \geq bd [/tex]

    Thus,
    [tex] 2(2^k) \geq (k+1)(k+2/{k+1}) [/tex]
    [tex] 2^{k+1} \geq k+2[/tex]
     
    Last edited: Jul 11, 2014
  6. Jul 11, 2014 #5
    You got it right for ##c##, can you now solve the equation ##d(k+1)=k+2## for ##d##?
     
  7. Jul 11, 2014 #6

    Maylis

    User Avatar
    Gold Member

    I got it now, but how the heck would I ever know to do that? I would have never guessed that would be the way to prove it. How is it logical to approach the problem in that manner? Also, how do I get the k+1 to be on the bottom of the fraction?
     
  8. Jul 11, 2014 #7
    Response to your edited post:

    You now found the relation ##c\gt d## to go from ##2^k\geqslant k+1## to ##2^{k+1}\geqslant k+2##. But you still need to prove that relation, do you know how to proceed?

    You got ##k+1## in the bottom of the fraction by solving for ##d##: $$d(k+1)=k+2\implies\require{cancel}d\cancel{(k+1)}\dfrac{1}{\cancel{k+1}}=(k+2)\dfrac1{k+1}\implies d=\dfrac{k+2}{k+1}.$$ The approach to this problem boils down to figuring out a way to go from ##2^k\geqslant k+1## into ##2^{k+1}\geqslant k+2##. It's basically just what AlephZero did but written in a more detailed manner.
     
  9. Jul 11, 2014 #8

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    Neither would I :smile:

    On the other hand, if you assume ##2^k \ge k + 1## and you want to show that ##2^{k+1} \ge (k+1) + 1##, then

    ## 2^{k+1} = 2(2^k) \ge 2(k+1) =2k +2 \ge k + 2## when ##k \ge 0##.
     
  10. Jul 11, 2014 #9

    Maylis

    User Avatar
    Gold Member

    Yes, for ##c > d##, you get ##2 \geq k+2/k+1 ##, which by algebraic manipulation is ## 2(k+1) \geq k+2##. How do I get the fraction to look like yours, with the fraction being on the bottom? As well as the slash going through indicating canceling a term.
     
  11. Jul 11, 2014 #10
    For the fraction use \frac{}{} for example \frac{x+2}{x+1} will produce ##\frac{x+2}{x+1}##. For the slash you first have to write \require{cancel} then to use the \cancel{} command where you put what you want to slash inside the brackets, therefore \require{cancel}\cancel{x+1} will produce ##\require{cancel}\cancel{x+1}##.
     
  12. Jul 11, 2014 #11

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I wouldn't call it "detailed". I would describe it a very confusing explanation which isn't very helpful for understanding the simple induction step.
     
  13. Jul 12, 2014 #12
    I could have proceeded as AlephZero (which is what I originally did but then got a warning with my post being deleted) but the OP specifically mentions that he didn't know where the need for ##2(k+1) \geqslant k + 2## came from.
     
    Last edited: Jul 12, 2014
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: Mathematical Induction
  1. Mathematical Induction (Replies: 2)

  2. Mathematical Induction (Replies: 9)

  3. Mathematical Induction (Replies: 6)

  4. Mathematical Induction (Replies: 5)

  5. Mathematical induction (Replies: 8)

Loading...