Discrete Math II - 5.2.1 Proof by Strong Induction
Vložit
- čas přidán 8. 06. 2024
- In this video we learn about a proof method known as strong induction. This is a form of mathematical induction where instead of proving that if a statement is true for P(k) then it is true for P(k+1), we prove that if a statement is true for all values from 1 to k (or whatever your starting value is), it is true for P(k+1).
Video Chapters:
Intro 0:00
What is Strong Induction? 0:07
Strong Induction with a Range of Values 1:12
Strong Induction with Specific Values 9:29
Up Next 16:14
This playlist uses Discrete Mathematics and Its Applications, Rosen 8e
Power Point slide decks to accompany the videos can be found here:
bellevueuniversity-my.sharepo...
The entire playlist can be found here:
• Discrete Math II/Combi... - Krátké a kreslené filmy
Literally, Professor Brehm saves the day every time. I got stuck wondering where do they get k>10 and came to this video and it is thoroughly explained. Not only that, now I fully understand strong induction.
Thank you! Happy I could help!
I am still not getting it.Please helppppppppppppppppppppp
This is the only strong induction video that make complete sense to me. Thank you for your explanation
i have watched countless videos on this topic. This is by far the best explanation. I finally get it. thank YOU so much. subscribed so quick. I'm going to watch all of these videos. Absolutely amazing. Thank you Professor Brehm. I'm passing my exam.
Your videos quite literally saved me from failing my discrete mathematics course. Thank you 🙏
I am really grateful for this wonderful explanation! I have been stuck at this point for a really long period of time. And I am very puzzled whenever Professor gives lecture. I finally understand it by watching your tutorial. Thank you so much!
I didnt understand anything
I’m so cooked bro
bro me too. if i don't get a 90 in this final i don't pass the class
Hurrah for these videos! 😄
Very nice examples and explannation. I was having trouble figuring out which base cases to include but your explanation around 11:30 really helped me see. I'll probably always make a table with arrows now :).
The prime example seems like circular logic since we assume P(j) for 2 ≤ j ≤ k but this isn't proven, except that's it's asserted for 2.
i agree. we really just made a hypothesis and then used that to justify the solution.
This is so helpful, thank you so much❤
You're so welcome!
Thank you so much, every dumb in internet is explaining the prime question really really bad. This helped too much...
This is helpful, but if everything is built on hypothesis after the base case how did we prove anything?
Thank you!
I’m kinda confused on why we assume p(j) is true for 2
I'm also confused- do we have to prove the inductive step or not? In this case it seems that we just assume it is true, but we never proved it... (meaning, we never proved that p(j) is true for 2
@@netanelkaye3014 it’s been while so I do understand it now.
Pretty much in weak induction you use the n-1 step to prove the nth step is true. (For example you use 2nd step to prove 3rd is true)
In strong induction you use all steps from n-1 to 0 to prove the nth step. (For example you use the n-1, n-2, and n-3, steps to prove the nth step is true)
The difference in notation is what makes it kinda confusing. in weak induction we normally use the n-1 to prove the nth step while in strong induction we use the nth and below to prove n+1 step. It’s the exact same concept though it’s just up to notation whether we want to prove the nth step or n+1 step
@@wavez4224 Right, but in weak induction, we do first prove the n-1 step. we dont just assume the n-1 step is true- we prove it. It seems like in this case, we dont prove all steps from n-1 to 0- rather, we just assume they are true. Am I wrong?
@@netanelkaye3014 you never prove the n-1 step in weak induction. You only prove the base case and that if you assume n-1 is true then n is true.
Same idea here. You prove the case case and then you prove that if all the steps between n and the base case are true then n+1 is true.
So we never prove the n-1 step in both weak and strong.
Hello professor, at 2:30, so like 2 can only be written as 2 * 1, but 1 is not considered a prime number. Maybe we have to add "or it is a prime itself" at the end.
agreed
This confused me also. A prime number cannot be represented as a product of primes, because 1 is not prime. I've read numerous texts on this that all assert that any n > 1 can be written as a product of primes. However, when they further explain the statement through proofs, they clarify that n is either prime OR a product of primes. Is this an accepted measure of ambiguity in a field that prides itself on precision?
@@tbnman It can be written as a product of 1 and itself (1). Further pedantry is unnecessary for this special case.
im assuming that you choose 10 in 10>=k because if it would be 9, then the initial value would not be 8; it would be 7. I think that is how I would have understood why 10
2 being a prime number is not a product of primes. How does the basis step become true?
If one of the multiple become prime; then it is enough to be a product of primes?
2=2•1
A prime number is a product of itself and the prime number one
will it be all right if I use k>10 instead of k>=10 , I still didn't understand why you used k>=10
I am sorry I am too silly. I am so confused.
the hypotheis only show that p(j) is true for 2
It’s a case we are considering. If k+1 is prime then it is true that k+1 can be written as a product of primes, and no more work is needed.
thanks
in 15:47, I am confused about why P(k-2) is true? we never proved it right?
We assume P(k-2) is true, which we can do since we have more than one initial condition. For instance, if P(k) is assumed true, then we know P(k-1) and P(k-2) are true since they are initial conditions.
technically 1 isn't prime so you can't use 2 as your first product of primes because 2 * 1 is not the product of two primes, it's the product of a SINGULAR prime.
I still do not understand why k>=10?
i love you kimberly
why cant you just use regular induction to show that you can make $0.08 stamps out of $0.03 and $0.05 stamps? Just use $0.08 as base case and then prove that if you can make $0.0k out of $0.03 and $0.05 then you can make $0.0k+1?
why onika burgers