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!

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


    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


    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