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: Help with this Induction proof

  1. Oct 23, 2008 #1
    1. The problem statement, all variables and given/known data

    I was reading my discrete math book and have this example of how they prove by induction that if 2x >(x+1)2 that 2k+1 >[(k + 1) + 1]2
    Where r>5


    3. The attempt at a solution

    2k+1 = 2 * 2k

    >2(k+1)2 by inductive hypothesis => How? And what happened the +1 in [(k + 1) + 1]2 Also shouldn't it be (k+2)2 if you but in k + 1 for x, so how is it 2(k+1)2

    = 2k2 + 4k + 2

    = k2 + 4k + 4 + (k2 - 2) => How?

    = (k+2)2 + (k2 - 2)

    >(k+2)2 => why do you ignore the (k2 - 2)?
     
    Last edited: Oct 23, 2008
  2. jcsd
  3. Oct 23, 2008 #2

    Mark44

    Staff: Mentor

    For an induction proof there are three parts:
    1. It has to be true for some starting point, typically for k = 0 or k = 1.
    2. You assume that the statement is true for n = k.
    3. Show that if the statement is true for n = k, it must also be true for n = k + 1.

    The problem you're looking at is slightly different in the numbering for my steps 2 and 3. They are assuming that the statement is true for n = k + 1 (the induction hypothesis -- a hypothesis is something that you assume is true), and then showing that it is also true for n = k + 2.

    One other thing, you have r > 5. Did you mean k?
     
  4. Oct 23, 2008 #3
    Sorry the r >5 was meant to be x >5 in 2x >(x+1)2
     
  5. Oct 23, 2008 #4

    HallsofIvy

    User Avatar
    Science Advisor

    No, that makes no sense. No formula in "x" will tell you anything about a different formula in "k". And there is no "r" in it! I suspect you mean that you are asked to prove that 2n> (n+1)2 for all n> 5. And one step in doing that will be to show that "if 2k> (k+1)2, then 2k+1> ((k+1)+1)2, the "induction hypothesis".



    The inductive hypothesis is that 2k> (k+1)2. To show that is true for the "next" k, you look at 2k+1= 2*2k. Since (the inductive hypothesis) 2k> (k+1)2, 2*2k> 2*(k+1)2. Putting those together, 2k+1> 2(k+1)2.

    They aren't there yet! They are starting from the left and showing that it gives the other side.

    Surely you know enough algebra to do that yourself.
    2k2+ 4k+ 2= k2+ k2+ 4k + 2= (k2+ 4k+ 2)+ k2 (I've just moved on "k2" to the end)

    Now, you should know that (k+ 1+ 1)2= (k+2)2= k2+ 4k+ 4. What we already have, k2+ 4k+ 2 needs to have 2 added to it to get that. Of course, in order to keep this true we also have to subtract 2:
    k2+ 4k+ 2+ 2+ k2-2


    Because it is larger than 0! We aren't showing "= " we are showing ">". Since k> 5 (remember that) k2- 2 is larger than 0 (in fact it is at least 23!). Adding a positive number to any number makes it larger.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook