Induction Inequality Proof Example 5: 2^n ≥ n²

Another viewer-submitted question. Inequality proofs seem particularly difficult when they involve powers of n, but they can be managed just like any other inequality given the right algebraic techniques!

[IffyProjects]

but i don't see how, when seeing a problem like this for the first time, you'd know to replace n^(2) by 2n + 1. I don't see how you would know to do that.

[halimjoshua]

hi! its very helpful, but I'm wondering how can you come up with the 2n+1 in the first place?

[yifpye]

8:36 I don’t get how you can say 7 is greater than/equal to 0...

[MaddSTATIC]

great video, it really helped me out! :)
The only problem i have is this: why do you assume that 2^n is greater than or equal to 2n+1? 

[Twannnn]

If anybody was wondering why 2^n > n^2 becomes 2^n * 2 > n^2 * 2 is because in order to get 2^n+1 you need to multiply 2^n by 2 (hence 2^n * 2). Since it's an inequality n^2 becomes n^2 * 2.

[alexanderbaron]

But how is 7 greater or equal to 0? How can we make that assumption, when 7 would never equal 0?

[kobilica]

You solved exactly same thing I got for homework, heh :D

Now I understand it completely.

[Wolfunt]

Why not use a chain for the first one?

For example:
assume: 2n + 1 <= 2^n
we need to show: 2(n+1) + 1 <= 2^(n+1)

2(n+1) + 1 can be rewritten as (2n+1) + 2 so we have part of our assumption in parenthesis.
(2n+1) + 2 <= 2^(n+1)

2n + 1 <= 2^n By assumption, we know this
(2n + 1) + 2 <= 2^n + 2 We can add two to both sides to get something similar to what we need to prove for our left hand side, and the statement will still hold true obviously using common
sense
2^n + 2 <= 2^n + 2^n Now we get to work getting our right hand side equal to what we need to show. We take the right hand side from the previous line (it now becomes the left side in this
scenario), and logically conclude that replacing 2 with 2^n will net you a greater value for all n >= 4
2^n + 2^n = 2 * 2^n Algebra
2*2^n = 2^(n+1) More algebra

So now, we have our right hand side equal to what we need to show as well. I think it's better to create a chain like this, rather than starting from what you need to show, which is a little strange

[johanfredrikberthlingherbe]

Nice video! One question though. Isn't the whole first part a bit unnecessary if you could simply prove that (2^k-(2k+1)) >= 0 for k>=4, which it is. Or am I not allowed to just insert 4 like that? 

[AmanKumar-utgh]

Sir, why m√a^n = a^n/m please explain

[kunalvshah]

@ 8:39, it should be > 0 not > or = 0 correct? if something is > or = 7, it is > 0 not > or = 0 right?

[mpcc]

How does one know the correlary piece they need to prove before hand?

[mmmmSmegma]

I'm already getting the feeling that this video is gonna be directly responsible for a love affair I' going to have with mathematics for the next year or so.

[asimami]

Can we do it by putting the equation on one side and zero on another side for every inequality

[aku]

I do it this way, hope it's correct.
2.2^k>=2.k^2
2^(k+1)>=(k+1)^2
To prove 2.k^>=(k+1)^2
2.k^2>=k^2+2k+1

True if k>2.4...

[tethyn]

Would you consider the first proof the lemma that you need for the current proof or proof in consideration? Good job:

[jameschen]

You are an excellent teacher, and that would be an understatement.

[snethembamsomi]

I don't get how you have two 2^k in 2.2^k. I'm confused

[RAKESHCHAUHAN-jmbt]

2.2power k
How convert 2 power k + 2 power z
Tell me

[beru]

You can go like a heat seaking missile right to the end. No need for ”expeditions” here and there.
1) Show that it is true for a smallest value of p. Bla bla
2) Assume the statement to be true for p.
3) Show that under the above assumption it is also true for p + 1. That is
(p + 1)^2 LE 2^(p + 1) expand on both sides p^2 + 2p + 1 LE 2 * 2^p that is p^2 + 2p + 1 LE 2^p + 2^p
Make use of our assumption under 2). That is, it now suffices to show that
2p + 1 LE 2^p.
But 2p + 1 LE p^2 since after we subtract 2p and add 1 we get
2 LE p^2 – 2p +1 LE (p – 1)^2,
which is true for p = 4, 5, 6, …
And again by our assumption under 2)
2p + 1 LE p^2 LE 2^p
Q. e. d.
Comment:
What we are as a whole to prove, and our assumption is like a balance leaning over to the right. We make use of our assumption and take away on both sides. The balance must not flip over to the other side! That is what suffices to prove. (And to do that we use our assumption once again.) Hope you see what I mean with a balance. The kind Mdm Justitia uses.