Explaining the Inductive Step of 2^n > n^2 for n > 4

[LittleTexan]

I have this question in my text that I can not understand

here it is

Show that 2^n > n^2 whenever n is an integer > 4.

the part in the answer that is confusing me is the inductive step

Here is what the text has for this part of the answer

Now we assume the induction hypothesis that 2^k > k^2 and want to derive the statement 2^(k+1) > (k+1)^2. Working from the right had side, we have (k+1)^2 = k^2 + 2k + 1 < k^2 + k + 1 = k^2 + 2k + k < k^2 + 3k < K^2 + k^2 (Since k > 3). Thus we have (k+1)^2 < 2k^2 < 2*2^k(by IH) which in turn = 2^(k+1)

Can someone please explain this to me?? Please

thanks

LT

 

[StatusX]

I think you may have copied that wrong. Check the book again, and try to find the step that's confusing you.

 

[LittleTexan]

Thanks. I have updated this statement (k+1)^2 = k^2 + 2k + 1 < k^2 + k + 1 = k^2 + 2k + k < k^2 + 3k < K^2 + k^2 (Since k > 3).

Sorry.

This is actually the part that I start to get confused on. (k+1)^2 = k^2 + 2k + 1 < k^2 + k + 1 = k^2 + 2k + k < k^2 + 3k < K^2 + k^2 (Since k > 3).

I understand this (k+1)^2 = k^2 + 2k + 1 but where does the rest of it come from.

Thanks

 

[Parlyne]

It makes sense if you just omit the part with $$k^2 + k + 1$$. That term does not obey either relation as purported.

If we ignore that, the rest follow pretty easily.

$$(k+1)^2 = k^2 + 2k + 1$$ trivially. Since we already know that $$1 < k$$, we can add $$k^2 + 2k$$ to both sides to get:
$$k^2 + 2k +1 < k^2 + 2k + k$$.

The second expression here simplfies to $$k^2 + 3k$$. And, since we know that $$3 < k$$, it must follow that $$3k < k^2$$. But, then, we see that:
$$k^2 + 3k < k^2 + k^2$$.

The right side of this, then, simplifies to $$2k^2$$.

So, this shows that $$(k+1)^2 < 2k^2$$ for all $$k$$ of interest. The rest you seem to be clear on already.

 

[LittleTexan]

Thanks for your response.

When you say add K^2 + 2k to both side are you added it to 1 < k? How do you know to use 1 < k?

where does the 3k < k^2 come from?? and where does (k+1)^2 < 2k^2 < 2*2^k come from??

 

[Parlyne]

I used $$1 < k$$ because that was what made sense based on what you had posted. Overall, this method isn't quite what I would do if posed with the problem.

$$3k < k^2$$ comes from multiplying both sides of $$3 < k$$ by $$k$$.

The argument I went through shows that $$(k+1)^2 < 2k^2$$. The induction hypothesis states that $$k^2 < 2^k$$; so, multiplying both sides by two gives the second piece of that last inequality.

 

[LittleTexan]

Thanks

Is there a better or a simplfied way of doing this?

 

[StatusX]

I don't think there is a much simpler way to do this. The idea is that when k increases by 1, 2^k doubles, so you need to show that k^2 increases by less, ie, (k+1)^2 < 2k^2. Then given that k^2 is initially (ie, at k=5) less than 2^k, this shows it will remain so for all k.

 

[Parlyne]

I would start from the other end.

$$2^{k+1} = 2*2^k > 2k^2$$, by the induction hypothesis.

Then, [tex]2k^2 = (k + (\sqrt{2} - 1)k)^2[\tex].

This means that [tex]2k^2 > (k + 1)^2[\tex] for all $$k$$ such that $$(\sqrt{2} - 1)k > 1$$. This condition becomes $$k > \frac{1}{\sqrt{2} - 1} \approx 2.414$$. Since we're only interested in $$k > 4$$, this shows that [tex]2^{k+1} > (k+1)^2[\tex].

 

[Parlyne]

I would start from the other end.

$$2^{k+1} = 2*2^k > 2k^2$$, by the induction hypothesis.

Then, $$2k^2 = (k + (\sqrt{2} - 1)k)^2$$.

This means that $$2k^2 > (k + 1)^2$$ for all $$k$$ such that $$(\sqrt{2} - 1)k > 1$$. This condition becomes $$k > \frac{1}{\sqrt{2} - 1} \approx 2.414$$. Since we're only interested in $$k > 4$$, this shows that $$2^{k+1} > (k+1)^2$$.

 

[matt grime]

I wouldn't start 'from the other end'. Why? Because the exam at the end will want to test the solver's ability to do induction, which is a useful if unenlightening tool.

In general, you learn from experience. One important lesson to learn, based on the OP's question "How do you know to use 1 < k?", is that when you look at a question you do not always expect to see how to solve it. You must play around with things until you get the right answer. I suppose if you just read the textbook it seems as if the writer instantly knows the correct method to employ. However, that is not how maths works. Dirac (or Feynmann) is supposed to have given a lecture once where he said: thanks for rewarding me with a prize for this clever idea of mine, I'd like to share with you the stupid ideas I went through before I came to this one.

You just play around with things until you see something that might help. You cannot expect to just write down the answer straight away.

 

[Parlyne]

It's still an inductive proof the way I approached it, since it still relies on the assumption $$2^k > k^2$$ to show that $$2^(k+1) > (k+1)^2$$. I was simply pointing what I find to be a simpler way of proving the inductive step.