Discrete Math II - 5.2.1 Proof by Strong Induction

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:

The entire playlist can be found here:

[valeriereid]

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.

[_fxglve]

Your videos quite literally saved me from failing my discrete mathematics course. Thank you 🙏

[JafarTheJackal]

This is the only strong induction video that make complete sense to me. Thank you for your explanation

[varshini]

you are the best teacher I have ever came across .... such a beautiful explanation with examples that clear the concepts .... love love ma'am

[eclipz]

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.

[jingyiwang]

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!

[VndNvwYvvSvv]

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.

[CrushOfSiel]

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 :).

[wavez]

I’m kinda confused on why we assume p(j) is true for 2<= j <= k. Are we just assuming that it’s true and then using that to prove itself? Isn’t it just circular reasoning then?

It seems like the question is only telling us that n>= 1 so I’m just kinda confused on where we got that from

[pibbxtra]

This is helpful, but if everything is built on hypothesis after the base case how did we prove anything?

[linaaveyaa]

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.

[mehmetalitoy]

Thank you so much, every dumb in internet is explaining the prime question really really bad. This helped too much...

[henryqiu]

I am sorry I am too silly. I am so confused.
the hypotheis only show that p(j) is true for 2<=j<=k. why you can say in case 1, that k+1 is prime, then p(k+1) is true
aren't you going to prove k+1 is prime?
otherwise, you can say that in the beginning without strong induction that k+1 is prime, then p(k+1)

[noobheadsigma]

2 being a prime number is not a product of primes. How does the basis step become true?

[AR-rgen]

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.

[leonben]

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

[jianqinggao]

This is so helpful, thank you so much❤

[MuhammadAbdullah-wxev]

will it be all right if I use k>10 instead of k>=10, I still didn't understand why you used k>=10

[AzimMukith]

I still do not understand why k>=10?

[akikozzm]

in 15:47, I am confused about why P(k-2) is true? we never proved it right?