# Help with this Induction proof

1. Oct 23, 2008

### Gear2d

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. Oct 23, 2008

### 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?

3. Oct 23, 2008

### Gear2d

Sorry the r >5 was meant to be x >5 in 2x >(x+1)2

4. Oct 23, 2008

### HallsofIvy

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.