Proving Induction: 2x >(x+1)2 | Help with Discrete Math Homework

[Gear2d]

Homework Statement

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

The Attempt at a Solution

2^k+1 = 2 * 2^k

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

= 2k² + 4k + 2

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

= (k+2)² + (k² - 2)

>(k+2)² => why do you ignore the (k² - 2)?

 

[Mark44]

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?

 

[Gear2d]

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

 

[HallsofIvy]

Homework Statement

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

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 2ⁿ> (n+1)² for all n> 5. And one step in doing that will be to show that "if 2^k> (k+1)², then 2^k+1> ((k+1)+1)², the "induction hypothesis".

The Attempt at a Solution

2^k+1 = 2 * 2^k

>2(k+1)² by inductive hypothesis => How?

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

And what happened the +1 in [(k + 1) + 1]²

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

Also shouldn't it be (k+2)² if you but in k + 1 for x, so how is it 2(k+1)²

= 2k² + 4k + 2

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

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

Now, you should know that (k+ 1+ 1)²= (k+2)²= k²+ 4k+ 4. What we already have, k²+ 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:
k²+ 4k+ 2+ 2+ k²-2

= (k+2)² + (k² - 2)

>(k+2)² => why do you ignore the (k² - 2)?

Because it is larger than 0! We aren't showing "= " we are showing ">". Since k> 5 (remember that) k^{2- 2 is larger than 0 (in fact it is at least 23!). Adding a positive number to any number makes it larger.}