Prove n! is greater than 2^n using Mathematical Induction Inequality Proof

Please Subscribe here, thank you!!! goo.gl/JQ8Nys
Prove n! is greater than 2^n using Mathematical Induction Inequality Proof

[@brysonrivera7026]

extremely helpful explanation! Makes a lot more sense now. I have been struggling with these M.I. proof inequalities, but you broke it down extremely well. Thank you!

[@rmb706]

I think the struggle has to do a lot with the fact that most of us aren't really accustomed to really using inequalities at first. Of course we are exposed to inequalities in basic algebra, but don't use them in this manner at all for quite some time. I remember how much I struggled with these two years ago. You may not even have to use this type of reasoning super often depending on which classes you choose but it definitely makes a big comeback in real analysis. You have to be a master of inequalities haha.

[@picnicbros]

But if you think about it, inequalities are so flexible, and could be much simpler to prove compared to equalities

[@existentialrap521]

Yep. I saw my professor adding stuff to the left of a statement by using inequalities. I was like wtf m8 you're breaking the rules. It's taking me a bit to make sense of it, but it's goin. on crip

[@michaelrislingnb306]

Proofs reallyyyy threw me for a loop and I just couldnt manage to understand certain things the prof did regarding inequalities. Ive watched a few of your proof videos and its really clarified what I am allowed to do and how I can structure my thinking with these sorts of proofs. There are tons of these types of proofs in my algorithm analysis class, so thank you from the bottom of my heart for putting these vids up. Bless you, you beautiful wizard.

[@graoliveira6688]

You have no idea how much I appreciate the fact that you did this in one screen! God bless you!

[@CardiganBear]

What is often not made quite clear in videos on this subject, and what greatly helps in grasping the principle of mathematical induction, is the fact that what we are attempting to show in the induction step, is NOT that the induction hypothesis itself is true, but that IF it is true, then it follows that the step with n = (k+1) is also true. Having shown that, and demonstrated that the statement is true for the base step, we then know that the statement must be true for all k.

[@morgard211]

Damn, this is hard. It's unconvetional and requires out of the box observations. Thanks man.

[@TheMathSorcerer]

Yeah the inequality proofs are hard for people to understand. When I first saw these many years ago I tried sooooo hard to understand them, and I couldn't do it man. Years later I tried again and it made sense. Nuts how hard some stuff is sometimes.

[@jasy0urs]

thanks alot dude, you pretty much taught me not to be afraid in using much more creative methods in math induction lol

[@TheMathSorcerer]

haha awesome

[@RKO1988]

Here is an alternate solution: Inductive Step: Assume P(k) holds, i.e., 2^k < k! for an arbitrary integer k ≥ 4. To show that P(k + 1) holds: 2^k+1 = 2^1∙2^k < 2∙ k! (by the inductive hypothesis) --> Makes no sense how it goes to the next line drops the 2. < (k + 1)k! = (k + 1)! Therefore, 2^n < n! holds, for every integer n ≥ 4. Idk why people leave out explanations to these. There's obviously an easier explanation to this. Same with how you got rid of the 4.

[@Xx-nd1rs]

I feel your sol is easier but i don't got it ... i stopped in 2^k+1

[@rdguezc]

Thanks for your video, but I really find it hard to understand why you used 1 in the substitution (min 5:25) right at the end of the exercise. I think you can't use any number less than 4 because that's a restriction of this problem. I wish you could provide us with some additional reference that would allow us to understand the reason for this substitution. Thanks in advance and again, great video.

[@martinepstein9826]

All he's saying is 4*2^k + 2^k > 1*2^k + 2^k which is clearly true.

[@FriggnH8ters]

Im new to proofs and this made no sense when I first listened to it. I sat for a few minutes and thought it through and eventually it clicked. I rewatched your explanation and it made sense, it was the most satisfying feeling ever finally understanding it.

[@darshandhande8903]

The cleanest explanation for proof for factorials by Induction on KZbin.

[@TheMathSorcerer]

Thanks man

[@Juniszapunis]

We had this in our beginners lecture and i was so confused. Thanks to you i finally got it :D

[@TheMathSorcerer]

Awesome !!

[@imoreo5338]

Why can't I understand the third part :(( there's a LOT of K's. I feel like my head is going to blow any minute

[@mozesmarcus6786]

1.) 4! = 24 > 2^4 = 16 2.) for n=4 holds n! > 2^n true 3.) 2^(n+1) = 2*(2^n) 4.) (n+1)! = n*(n!) 5.) n! will only remain greater than 2^n if n! grows faster than 2^n 6.) We have shown in 3.) and 4.) that the growth factors for n! and 2^n are n and 2 respectively. 7.) For n>4 holds n>2, thus n! grows faster than 2^n All of the 7 steps can be combined to prove n! > 2^n for n >= 4 Hopefully this proof is a little more clear. This has been quite a simple statement to prove.

[@mozesmarcus6786]

Correction: (n+1)! = (n+1)(n!) != n*(n!) This was a very stupid mistake

[@cool-nb8gu]

if the question was asking you to prove n! > 2^n would you use a different value than 1 when writing the last few steps? I'm guessing it would be 2 instead of 1? that would give: 2 * 3^k + 3^k , which gives us 3 * 3 ^ k which gives us 3^(k+1)

[@legend7890]

Here is my solution. I might have done the third step from last wrong. Please provide feedback. Thanks n! > 2^n n>=4 1. Basis: 24 > 16 2. Induction hypothesis: k! > 2^k for k>=4 3. Prove true for k+1. to prove: (k+1)! > 2^k+1 (k+1)! =(k+1)k! factorial definition >(k+1) 2^k. induction hypothesis >(4 +1)2^k. k >=4. >(1+1)2^k. 4>=1. (this step might be wrong or maybe I could have added 4+1 in the previous step and replace 5 by 2 since 5>=2) =2.2^k =2^k+1

[@martinepstein9826]

The third to last step is correct. This is a good solution. My only qualm is you wrote "k >=4" and "4>=1" in the right column. You really need the strict inequality here: k>4 and 4>1

[@galou4308]

Thank you very much for this video ! I am struggling with proof by induction and this made it a bit clearer

[@samuelhawksworth1923]

I have such a hard exercise task, prove n!>n^m for n>=2m+1. Ive managed to do the base step but the rest is solid as a wall

[@amanhamu4295]

Hello 👋 first of all I want to say thank you And then quality of some video is May have some problem so Pls try to correct my teacher Second not only maths we need physics phsyco logic as well as work sheet thank you very much

[@sephirofthx3600]

someone give this man a medal!

[@joelmhaske8185]

I'm struggling to understand everything after 4:18 wherein you plug in the values of RHS... I'm just lost. How does it happen?

[@tauceti8341]

by defn of product rule for exponents: a^(m) * a^(n) = a^(m+n) 2^k * 2^(1) = 2^(k+1) by defn of multiplication 2*2k = 2k + 2k by defn - A Factorial of a positive number is the product of all the positive numbers less than the number and the number itself. thf (n+1)!=(n+1)n! ex. (4+1)!=(4+1)4! 5!=5(4!) 5!=5(*4*3*2*1) thf. (k+1)! = k(k+1)! 4:26 subbing all k! for 2^k (RHS) 5:31 subbing this time for k>4 5:50 by defn of multiplication again 2k*2 = 2k + 2k

[@AloneMaru]

Amazing explanation! That greater than substitution trick is quite nice!

[@TheMathSorcerer]

thank you!

[@maxamedaxmedn6380]

At the ending what if I just write K×2^k + 2^k >= 2^k + 2^k Cancel 2^k in the equation Then we get k×2^k >= 2^k and it is solved for k>=4

[@finmat95]

Just observer that 4! = 24 and 2^4= 16, so the inequality is already true for n = 4, for n+1 we've: (n+1)! > 2^(n+1) -> n*n! > (2^n)*2^1 Suppose n! > (2^n) is true, then what is the difference between n and n+1 in the inequality? n and 2^1, since n is always bigger than 2^1 for any n>4 the inequality remains true.

[@Chrisymcmb]

I am a little confused with the 4>=1. Yes this is true, but how does this constitute for replacing the RHS of the expression from >=4(2^k)+2^2 to >1(2^k)+(2^k)?

[@martinepstein9826]

I'm confused why you're confused. If you agree that 4(2^k)+2^2 is greater than 1(2^k)+(2^k) why would you be opposed to writing 4(2^k)+2^2 > 1(2^k)+(2^k) in the proof?

[@ianmi4i727]

The kind of exercises we did in Calculus I ! (first chapters: Logic, Higher Algebra)

[@TheMathSorcerer]

Oh wow haha

[@ianmi4i727]

@@TheMathSorcerer 😊

[@Dextagon]

Great video, couldve removed the title tho, it took up almost 30-40% of the screen

[@MLGJuggernautgaming]

Can you not have a factorial in the proof? Why not just say k!(k+1) > k!(2) and be done?

[@metal079]

Thank you for the explanation, Zybooks is garbage at explaining the steps.

[@oceansxstars]

Can you explain why you’re replacing the 4 with a 1 instead?

[@TheMathSorcerer]

yeah, so basically I wanted just 2^k, so that I could add them 2^k + 2^k = 2*2^k = 2^(k + 1), so I KNEW I wanted 2^k, so I purposely chose 1 so that it would work

[@platipus1987]

@@TheMathSorcerer so can k be any integer? if say i need 7 or 9? is it limited by anything?

[@DiegoLuna-qf1bl]

@@platipus1987 Since you're trying to prove that (k+1)! is greater than 2^(k+1), choosing 1 will help you by condensing that portion into something more pleasant where in this case it will give you 2^(k+1) when you choose 1 as your integer. You could have chosen any integer but because we want to prove that it is greater, then by using 1 it will help us to get 2^(k + 1) to show that it is indeed less than (k+1)! .

[@amir3515]

@@platipus1987 limited by 4 because K is greater than or equal to 4 so if you say 7 or 9, it's not true, k is not greater than or equal to 7 or 9. It's greater than or equal to 4 so by that logic it is DEFINITELY greater than 3 or 2 or 1 so that's why you can choose 1

[@cuentaparaaprender5941]

that was nice, thanks,I had to see the video 2 times.The structure would be 1.test 2.Hypothesis 3. Demonstration: basically replace k+1 in place of n and rewrite cleverly the right hand side so that we get some terms equal to the RHS of our Hypothesis. Then, we procreed to develop the LHS of the demonstration looking to get replaceable terms for those of the hypothesis, so that way we have LHS and RHS in terms of our hypothesis, and then is easy to compare which of these have the bigger di⁕⁕⁕ excuse me, value.

[@mikemoke10]

The fact that you finish the whole proof in one page makes me think you a savage

[@nicholas3130]

This video helped so much! Thank you!

[@TheMathSorcerer]

That's awesome!!

[@oneboyonegame4197]

I am a foundation year student and I don’t understand why I am studying complex proofs

[@fndTenorio]

I just multiplied both sides by (k + 1): (k + 1) k! > 2^k (k + 1), (k + 1)! > (2^k) * 5 > (2^k) * 2, (k + 1) > 2^(k + 1).

[@zahidgul7254]

took me a very long time to understand this whole thing. but hey, i got it. thanks man for your help.

[@nal8112]

please help me understand why you can turn 4(2^k)+2^k into 2^k + 2^k simply because 4 is greater than 1.

[@ummehany5815]

Thanks sir,from Bangladesh

[@TheMathSorcerer]

you are welcome:)

[@joaoc9038]

But cant i just do it like this: n!>2^n. n>=4 implies that n+1>2>0. (n+1)n!>(2).2^n

[@elijahwehrhahn2503]

This was beautiful. riveting. appreciate it

[@jameyatesmauriat6116]

At 3:39 i didn’t really figured it out until I wrote it down although it may be very simple to others, I was thinking how 2.2^k equals 2^k+2^k 😮

[@alwalid511]

you are such a fkn legend man THANK YOU!

[@BooleanDev]

thanks it makes so much more sense with this explanation

[@TheMathSorcerer]

Glad to hear that!

[@BooleanDev]

@@TheMathSorcerer yea my professor skipped straight from (k+1)2^k to 2*2^k, and i was like tf how if that possible

[@BM-ls8tp]

I just got even more confused by that last part.

[@shwetachauhan9766]

Thanks man, you made my day!!!

[@TheMathSorcerer]

👍

[@cuentaparaaprender5941]

that 2 to the k + 2 to the k = 2 to the key x 2 was unexpected, but yeah, this make sense.

[@henri1_96]

This was very helpful. I just wish you had explained (k+1)!=(k+1)k! a bit more. I had to do some google searches for that one. :)

[@imoreo5338]

Hmmm I think he added (k+1) to both sides on that part hehehehe

[@user-xi2xf1jj2m]

Remember if you have 5! for example, then its equal to 5(4)(3)(2)(1), so basically we are subtracting 1 each time and keep multiplying the numbers together until we reach the number 1. Also, you can rewrite 5! as 5(4)! and you will get exactly the same result, which is the case in this video.

[@itsdennyy]

GOD BLESS YOUR SOUL MAGIC MAN.

[@Hello_am_Mr_Jello]

You killing it , thanks

[@TheMathSorcerer]

You are welcome!

[@RayanL]

thanks you from france 👍

[@TheMathSorcerer]

awesome, france! No problem at all:)

[@TheBoDuddly]

So clear, thank you!❤

[@carljuanhill]

Richard Feynman-esque. Explained simply, giving those little insights to assist along the way. Thank you Math Sorcerer!

[@TheMathSorcerer]

Thank you!!

[@federicaangelotti8885]

And if instead of n!, I' have had (n+1)! ? Please help

[@fannie_hrbc5205]

waw super great thanks 😭🙏

[@dangahng9911]

how is 2^k*2^1 is equal to 2^k + 2^k? I just don't understand that 2^2k is equal to 2^k

[@dangahng9911]

3:07

[@dangahng9911]

nvm, I got it. great video, thumb up.

[@TheMathSorcerer]

yeah that's one of the tricky parts, it's hard right!!! Glad you finally got it:)

[@RKO1988]

@@TheMathSorcerer can u explain

[@alexcampbell8963]

why would you squash the proof in the corner tho

[@satoruai3475]

This is help me to do my hw. Thanks so much.

[@KentViscount]

I am lost on how you dropped the >=4 and made it >1

[@TheMathSorcerer]

Because 4 is bigger than 1 so you can do 4greater than 1

[@KentViscount]

@@TheMathSorcerer Unfortunatly I don't understand how you are making that substitution. I seem to be missing something

[@TheMathSorcerer]

@@KentViscount it's ok people have a hard time with this step but it's simple once you understand. Ok so do you agree that 4 is bigger than 1? So it's just saying that, 4 >1. We could have done 4> 2 or 4> 3 etc. The number 1 was chosen because it makes the proof work. If you had say 4*3 +4*7 we could say 4*3+4*7>4*1+4*1 because 4>1, you just replace the 4 with the 1

[@RKO1988]

@@TheMathSorcerer It doesn't make any sense how it disappears. I guess I never was taught you can replace #s in an inequality expression freely

[@mallison521]

Can someone point me to a link or something that explains the strongest inequality he talks about? How would I decide what the strongest inequality is? What does that mean?

[@hcmcnae]

> is stronger than >= because it leaves out the possibility of both sides being equal, hence why > is the 'strongest' inequality

[@vansf3433]

That one is too easy Try this one : ( 2n)! > n^n for all values of n

[@sucheta_s_room]

Why you putting 4=1 ?

[@georgemihaylov2381]

Great explanation!

[@ImBathMan]

You need to make the induction step more understandable by using the fact that S_k implies S_(K + 1). Teach it as though it was a conditional statement.

[@alandaniels2095]

Use Mathematical Induction to show that n!>= 2 n-1 for n=1,2,....

[@yirmeyahuM]

Lost me on the third part man

[@mazenabouelhassen4913]

Thank you so much!

[@rupsamondal6347]

thanks sir from India

[@valzugg]

You lost me at the spot where you put the 4 in

[@markdavies7027]

Could someone please check my work: (k+1)! = (k+1)k! > 2k! (since k >3) >2x2^k (from inductive step) =2^(k+1).

[@fantahunmengistu9221]

you made it more difficult......

[@mozesmarcus6786]

1.) 4! = 24 > 2^4 = 16 2.) for n=4 holds n! > 2^n true 3.) 2^(n+1) = 2*(2^n) 4.) (n+1)! = n*(n!) 5.) n! will only remain greater than 2^n if n! grows faster than 2^n 6.) We have shown in 3.) and 4.) that the growth factors for n! and 2^n are n and 2 respectively. 7.) For n>4 holds n>2, thus n! grows faster than 2^n All of the 7 steps can be combined to prove n! > 2^n for n >= 4 Hopefully this proof is a little more clear. This has been quite a simple statement to prove.

[@jaamalarane959]

very well explained

[@TheMathSorcerer]

thank you!!

[@nafisfuadshad7377]

where i=does the 4 goes"

[@ciandoyle3315]

omg you saved me again

[@TheMathSorcerer]

Awesome !

[@nonyelumkenechukwu50]

You messed up at the end bruh

[@ryanjohnson2844]

This is harder than calc2 ._. Or is it just me

[@ultron1060]

beautiful

[@adinaimazurova2003]

you are cool!

[@nadiiusmail5665]

Well

[@sairamalik0]

Can't understand 🥺

[@TheMathSorcerer]

i'm so sorry

[@maratibali1919]

perfecto

[@darkhunter5224]

😎😎😎😎🙏🙏🙏🙏🙏🙏

[@darkhunter5224]

Indian

[@moutonguerrier]

[@tolulopefamurewa6135]

Dude you ain't communicating

[@hirako9326]

Problem tookup 50% if the screen, and squeezing the answers to the bottom corner🥲

[@TheMathSorcerer]

LOL!!!!!!!!!! I wonder why I did that hahahaha.

[@hirako9326]

@@TheMathSorcerer hahaha thanks for the tutorial tho, it helps🤣