Proof: 2^n is Greater than n^2

We do a fun inequality proof: 2^n is greater than n^2 for n greater than 4 using mathematical induction. This is a tricky induction proof as far as introductory proofs go, but by focusing on where we need to go, we'll be able to take care of business in short order! #Proofs

★DONATE★

Thanks to Robert Rennie, Barbara Sharrock, and Rolf Waefler for their generous support on Patreon!

Follow Wrath of Math on...

[antariowoods]

By far this is the best explanation to this problem I have ever seen. It takes patience but boy is it rewarding to finally understand it. thanks a lot! Subscribed
(my final is tomorrow morning)

[nathanielcabansay]

This is surprisingly useful for when you want to know why an algorithm with a time complexity of O(2^n) performs worse than one with a time complexity of O(n²)

[Morejamsthanjimin]

Thank you! I never understood when my prof explained induction, but with your explanation I understood immediately!

[stoopidoo]

My university course on mathematical methods for physics (maybe it's called that in english, maybe not) just begun and this was the first problem for us to prove in our homework. I've managed to get toward rewriting 2^(n+1) and solving the binomal on my own but due to never having been confronted with induction before, I quickly ran into troubles afterwards. Your video really helped me grasp this problem (massive thanks), tho I will definitely need a lot more practice to become comfortable with induction.

[benjaminvatovez]

Thank you for this video! To people who are less intuitive or less experienced like me, I would suggest to do it this way for any k > 4 :
First, 2^(k+1) = 2 . 2^k > 2 . k²
and then 2k² > (k+1)² if and only if k²-2k-1 = (k-1)² - 2 > 0, which is true as (k-1)² - 2 > (4-1)² - 2 = 7 > 0

[ratmouse]

I agree that this has been the best explanation I've found. Finally get it!

[guilhermemonteiro]

The best explanation I found on youtube!

[shoopinc]

Thank you, great example of using the information about the integers of interest to run induction.

[Mymath.]

Greetings from Turkey, this video's really useful thank you 🙏🏻

[niha]

thank you so much for your efforts my youtube sir

[concept-math]

question no. 32. .
why we ignored that term.
there should be some reason behind

[firstname]

this was a great explanation -- but my class wants it done by minimum counterexample (:

[mymentalhealthjournal]

Where did the 1 come from? Why did you suddenly say that 8 is greater than 1, why is it specifically 1? Or do we let it be specifically 1 because we want to make it become k^2+2k+1?

[anty.]

where did the assumption of k*k being greater than 4k come from? like i get it has to do with k being greater than 4 but i don't know what mathematical rule this is. i'm a sophomore taking discrete math and i haven't done any math for over a year lol
edit: nvm i get it, since the minimum of k is 5 then that means that k*k is equivalent to at least 5*5 rather than only 4*5

[gani]

2^n is not greater than n^2 for n = 2, 3 or 4.

[aleggs]

wait so why do we ignore 0 and 1 and jump straight to n = 4? someone please explain. do we just ignore those for some reason?

[jcn]

3:31 is wrong you cant just double up both sides

[tapashgayen]

This is not tricky it's easy it come in our exam only 2 marks

[zykrzys]

Help me,
What's length and width