2^n is greater than n^2. Strategy for Proving Inequalities. [Mathematical Induction]

In this video, I showed how to prove inequalities by mathematical induction.

[anikethkopalle]

probably the best explanation on youtube. great stuff! thanks!

[idellius]

I have been struggling with this proof for a while, and every explanation I've found about it just didn't click for me. You put this together in a way that no other YouTube lecturer could. Thank you for saving my sanity brother!

[ANIMEPLANET-tn]

thank you for making this video. It was really useful for me.

[madonnacesso]

I love your videos man! From Italy 🇮🇹, never stop learning

[davide]

thank you very much you definitly need more views

[shmuelzehavi]

Very nice approach end explanation.
I'll present another approach, for the proof that:
[∃ m ∈ N, m > 4, 2^m > m^2] ⟹ [n = m + 1 ⟹ 2^n > n^2]
Proof:
2^m > m^2 ⟹ 2^m - m^2 > 0
Therefore, for n = m + 1 we obtain:
2^n - n^2 = 2^(m+1) - (m+1)^2
= 2⋅2^m - m^2 - 2m - 1
= 2(2^m - m^2) + (m-1)^2 - 2
> (m-1)^2 - 2 > (4-1)^2 - 2
= 7
> 0
Therefore: 2^n > n^2 ∎

[EzraSchroeder]

this one is straight out of an advanced calculus book haha! it is a problem in chapter one of Kenneth A. Ross: Analysis the Theory of Calculus -- love it!

[robertveith]

*Everyone, * here is a modified approach:

The base case is for n = 5.
2^5 vs. 5^2
32 > 25
So, the base case is satisfied.

The inductive step. Assume it is true for n = k, for k >= 5:

That is, assume 2^k > k^2.

Then, show it is true for n = k + 1.

That is, show 2^(k + 1) > (k + 1)^2.

Take the inequality in what we are assuming and multiply each side by 2
so that it resembles closer to the inequality that we want to show:

Assume: 2^k > k^2
2*2^k >2*k^2
2^(k + 1) > 2k^2

We ultimately need to show 2^(k + 1) is greater than (k + 1)^2 for k >= 5.
If we can show that 2k^2 is greater than (k + 1)^2, then we can use the
transitive property to finish this.

2k^2 vs. (k + 1)^2
2k^2 vs. k^2 + 2k + 1
2k^2 - k^2 - 2k vs. 1
k^2 - 2k vs. 1
k^2 - 2k + 1 vs. 1 + 1
(k - 1)^2 vs. 2

By inspection, you can see that for k >= 3, the left-hand side is greater than 2.

So, 2^(k + 1) > 2k^2 > (k + 1)^2.

By transitivity, 2^(k + 1) > (k + 1)^2.

Thus, by the Principle of Mathematical Induction, I have shown that
2^n > n^2 for all integers n greater than or equal to 5.

[No.School.dk_Colur]

That little tmr song/ intro was so sweet

[Loots]

took me a bit to not be confused but i get it, amazing

[vpikosh]

Great content man, thank you so much for the explanation. Now would the proof change if instead of strictly greater than we had a greater or equl than? Like 2^n >= n^2

[shuaibjemil]

Thanks sir.Waiting for maths induction for questions in Matrix form

[abioolayoyledegil]

Thank you for this very informative video!Im freshman in college and we had induction topic 3-4 weeks ago and i remember doing this exercise or similar to this one in class. My question is instead of step by step making it smaller in 6:51 can we just say 2k+1 is less than k² because k is starting from 5? Does that work too?

[rooseveltpantaleonvara]

Thank you, this was a great explanation I finally got it.

[tgx]

I had also some idea. 2^n-n^2>0, (2^n/2-n)(2^n/2+n)>0, So this Proof Is ekvivalent with the Proof 2^n/2>n by induction...
sqrt2*2^n/2>n+1 for n+1, sqrt2=(1+ something Positive). Sometimes I like combinations Proofs.

[EzraSchroeder]

where'd you get your hat? i might need one...

[HowlingDeath]

k^2> 2k+1

What I don't get is how can put least value of k=4 in above eq?

[dnaingnaing]

May I ask that if it doesn't work for k =5, Can I work out to prove k=6and if k=6works out does that mean P(n)is true for k greater than 4.

[giggablob]

i will never understand induction with inequalities cus i can wrap my brain around the fact, that i can js change the value like that 😭

[Ruth-bepm]

Make a video specifically for me because I still don't get it 😢