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.
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.
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.
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
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
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.
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
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
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
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!
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.
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 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)! .
@@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
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)?
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?
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)
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.
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?
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.
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.
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.
@@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
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.
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.
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.
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.
![2^n is greater than n^2. Strategy for Proving Inequalities. [Mathematical Induction]](/img/n.gif)
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
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.
Correction: (n+1)! = (n+1)(n!) != n*(n!)
This was a very stupid mistake
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.
All he's saying is 4*2^k + 2^k > 1*2^k + 2^k which is clearly true.
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.
But if you think about it, inequalities are so flexible, and could be much simpler to prove compared to equalities
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
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?
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
thanks alot dude, you pretty much taught me not to be afraid in using much more creative methods in math induction lol
haha awesome
Damn, this is hard. It's unconvetional and requires out of the box observations. Thanks man.
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.
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
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
We had this in our beginners lecture and i was so confused. Thanks to you i finally got it :D
Awesome !!
Thank you for the explanation, Zybooks is garbage at explaining the steps.
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
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!
Great video, couldve removed the title tho, it took up almost 30-40% of the screen
I am a foundation year student and I don’t understand why I am studying complex proofs
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.
Can you explain why you’re replacing the 4 with a 1 instead?
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
@@TheMathSorcerer so can k be any integer? if say i need 7 or 9? is it limited by anything?
@@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)! .
@@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
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)?
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?
Amazing explanation! That greater than substitution trick is quite nice!
thank you!
Lost me on the third part man
Can you not have a factorial in the proof? Why not just say k!(k+1) > k!(2) and be done?
This video helped so much! Thank you!
That's awesome!!
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
Thank you very much for this video ! I am struggling with proof by induction and this made it a bit clearer
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)
Thanks sir,from Bangladesh
you are welcome:)
😎😎😎😎🙏🙏🙏🙏🙏🙏
Indian
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 😮
you made it more difficult......
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.
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
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.
The kind of exercises we did in Calculus I ! (first chapters: Logic, Higher Algebra)
Oh wow haha
@@TheMathSorcerer 😊
someone give this man a medal!
you are such a fkn legend man THANK YOU!
I just got even more confused by that last part.
Use Mathematical Induction to show that n!>= 2 n-1 for n=1,2,....
This was beautiful. riveting. appreciate it
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?
> is stronger than >= because it leaves out the possibility of both sides being equal, hence why > is the 'strongest' inequality
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
3:07
nvm, I got it. great video, thumb up.
yeah that's one of the tricky parts, it's hard right!!! Glad you finally got it:)
@@TheMathSorcerer can u explain
thanks you from france 👍
awesome, france! No problem at all:)
And if instead of n!, I' have had (n+1)! ?
Please help
waw super great thanks 😭🙏
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.
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.
The cleanest explanation for proof for factorials by Induction on TH-cam.
Thanks man
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.
why would you squash the proof in the corner tho
Can't understand 🥺
i'm so sorry
beautiful
Could someone please check my work:
(k+1)! = (k+1)k! > 2k! (since k >3) >2x2^k (from inductive step) =2^(k+1).
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
GOD BLESS YOUR SOUL MAGIC MAN.
Thanks man, you made my day!!!
👍
The fact that you finish the whole proof in one page makes me think you a savage
I am lost on how you dropped the >=4 and made it >1
Because 4 is bigger than 1 so you can do 4greater than 1
@@TheMathSorcerer Unfortunatly I don't understand how you are making that substitution. I seem to be missing something
@@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
@@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
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.
You messed up at the end bruh
You lost me at the spot where you put the 4 in
That one is too easy
Try this one : ( 2n)! > n^n for all values of n
that 2 to the k + 2 to the k = 2 to the key x 2 was unexpected, but yeah, this make sense.
You killing it , thanks
You are welcome!
thanks it makes so much more sense with this explanation
Glad to hear that!
@@TheMathSorcerer yea my professor skipped straight from (k+1)2^k to 2*2^k, and i was like tf how if that possible
This is harder than calc2 ._. Or is it just me
took me a very long time to understand this whole thing. but hey, i got it. thanks man for your help.
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).
you are cool!
This is help me to do my hw. Thanks so much.
omg you saved me again
Awesome !
You have no idea how much I appreciate the fact that you did this in one screen! God bless you!
Why you putting 4=1 ?
Well
So clear, thank you!❤
very well explained
thank you!!
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. :)
Hmmm I think he added (k+1) to both sides on that part hehehehe
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.
perfecto
where i=does the 4 goes"
Great explanation!
Thank you so much!
thanks sir
from India
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.
I feel your sol is easier but i don't got it ... i stopped in 2^k+1
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.
Richard Feynman-esque. Explained simply, giving those little insights to assist along the way. Thank you Math Sorcerer!
Thank you!!
Dude you ain't communicating
Problem tookup 50% if the screen, and squeezing the answers to the bottom corner🥲
LOL!!!!!!!!!! I wonder why I did that hahahaha.
@@TheMathSorcerer hahaha thanks for the tutorial tho, it helps🤣
thank you