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!

Principle of Induction

  1. Mar 3, 2009 #1
    1. The problem statement, all variables and given/known data

    Prove that for each [tex]n \in N[/tex] (aka natural numbers), [tex]2^n \geq n+1[/tex]



    2. Relevant equations


    3. The attempt at a solution

    Let the proposition P(n) be "[tex]2^n \geq n+1[/tex]"

    Clearly P(n) is true for n=1, [tex]2^1 \geq 1+1[/tex].

    We suppose P(k) is true, i.e., supposing that [tex]2^k \geq k+1[/tex] is true, then,

    [tex]2^{k+1} \geq (k+1)+1[/tex]

    I think it can then be rewritten as [tex]2.2^{k} \geq 2.(k+1)[/tex]. Does anyone know the next step? I'm not sure what to do from here...

    Thanks!
     
  2. jcsd
  3. Mar 4, 2009 #2
    well, your induction hypothesis is:

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

    now

    [tex]2^{k+1}=2*2^k\geq 2(k+1)=2k+2>(k+1)+1[/tex]
     
  4. Mar 4, 2009 #3

    Mark44

    Staff: Mentor

    Omit the line above, since that's where you want to end up. Just say:
    suppose P(k) is true, i.e., that [tex]2^k \geq k+1[/tex]
    Keep it in the back of your mind where you want to go, but work toward that goal.
    So you have 2k + 1 = 2 * 2k >= 2 * (k + 1) = 2k + 2

    How does that last expression compare with k + 2? (I.e., (k + 1) + 1)
     
  5. Mar 7, 2009 #4
    So, it is [tex]2^{k+1} = 2.2^k \geq 2.(k+1)[/tex]

    [tex]2(k+1) = (k+1)+(k+1) \geq (k+1)+1[/tex]

    I'm a little confused, how should we make the conclusion?
    Since (k+1)+1 is supposed to be less than or equal to [tex]2^{k+1} (= 2.2^k)[/tex], and now we know it is less than or equal to 2.(k+1). Therefore...
     
    Last edited: Mar 7, 2009
  6. Mar 8, 2009 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    No, "(k+1)+(k+1)" is not the point. As Mark44 said before, 2(k+1)= 2k+ 2. Now, since k is a positive integer, it is certainly true that 2k> k (you might want to do another induction to prove that formally) so 2k+ 2> k+ 2= (k+1)+ 1.

     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Principle of Induction
  1. Mathematical induction (Replies: 3)

  2. Proof by induction (Replies: 1)

  3. Proof by Induction (Replies: 3)

Loading...