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: Simple Induction Proof

  1. Sep 13, 2010 #1
    1. The problem statement, all variables and given/known data

    Prove by induction on n that n belonging to N (set of natural #'s)
    2n > n

    2. Relevant equations



    3. The attempt at a solution

    So here's my stab at it!

    Base case: n = 0 (My prof includes 0 in N)

    20 > 0, 1 >0
    True. So this works for the base case.

    Assume this holds for n. Let n = k+1

    2(k+1) > k + 1

    Here is where I'm a bit confused..
    I'm not sure if it should be:

    2(2k) > k + 1
    > 2k

    OR

    2k + 1 > k + 1

    And with either one, how do I continue??

    Eekkk. any help is appreciated! Thanks.
     
  2. jcsd
  3. Sep 13, 2010 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You tell me. Is 2^(k+1) equal to (2^k)+1 or is it 2*(2^k)? You must know something about how exponents work, right?
     
  4. Sep 13, 2010 #3

    jgens

    User Avatar
    Gold Member

    This is perhaps a bit nitpicky, but you should probably write 20 = 1 > 0.

    This should be something along the lines of: "Assume this relation holds for the natural number k. If we can show that this implies that the relation holds for the natural number k+1, then we know that it holds for all natural numbers."

    Granted, my statement is quite verbose, but it makes it clear in what direction the proof is headed and doesn't leave near as much room for confusion.

    I think that you've managed to confuse yourself here. By the statement above, you already know that 2k > k. All you now need to show is that 2k+1 > k+1 must be true. To do this, note that 2k+1 = 2*2k > 2k. Now, can you prove that 2k > k+1?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook