1.8.4 Strong Induction: Video

Показать описание

MIT 6.042J Mathematics for Computer Science, Spring 2015
Instructor: Albert R. Meyer

License: Creative Commons BY-NC-SA

Рекомендации по теме

Комментарии

Hey, This is for those who don't get it, like I did ... Why do we use strong induction in postage example? Because we need to prove not only the base case (like in induction), but + two cases after it. Why? If we able to get three consecutive numbers (e.g. 8<-base case, 9, 10) we can get any number more then 8, adding 3 for every of particular cases. 8+3 = 11, 9+3 = 12, 10+3 = 13 and so on 11+3 = 14, 12+3=15, 13+3 = 16. Now I have 9 numbers (8, 9, 10, 11, 12, 13, 14, 15, 16). And I can do it infinitely and get all the numbers >=8.
Formula for making P(n) = 0+8 cents depends on the making P(n-3) cents, P(n+1) depends on the making P(n-2). P(n+1) = P(n-2) + 3.
We have to directly prove three BS for 8, 9 and 10 (P(0), P(1) and P(2)). We must construct it using only 3s and 5s. And I can definitely do it: P(0) = 8 is one 5 and one 3, P(1) = 9 is three 3s, P(2) = 10 is two 5s.
We have shown how to get cents for every value of P(n) from 0 to some m, where 0<=m<=n (in other words how to get values from 8 to ... 10). Next we need to prove that our P works for m+1 case. We know that the biggest base case P(2) = 10, then our P(m+1) >= 11. Subtract 3 cents for each side P(m+1)-3 >= 8 . We know how to construct 8 with some amount of 3s and 5s. P(m+1) - 3 = let say a*3+b*5 (where a and b are non negative ints). Then P(m+1) = a*3+3+b*5 or (a+1)*3+b*5 is also combination of 3s and 5s. It's what we needed to prove. And we have proved it. I'm not afraid to take P((m+1)+1), because I have the second base case proved P(1) = 9.

guitareter

I came into the comments expecting a slew of: "Oh my god, my teacher couldn't explain induction properly, but you did it so well! Thank you so much!"
While I'm sitting here, thinking to myself: "what the heck did I just watch?"
The explanations the lecturer gave were off-kilter with the text seen on screen, often I'd have to close my eyes and ignore what's on the screen to actually catch w/e is being said. Leaps and logic are seemingly being made, with no attempts to properly ILLUSTRATE them, instead of just saying that it works so it works.

Looking at the uploader's name, that makes total sense, though. One of the commenters was right, this is the sort of poor explanations people come to youtube to remedy.

TrojenMonkey

The "intuitive hand-wavy argument" ( 0:56 ) really helped me understand it :) Thank you.

westronic

This is exactly the kind of poor explanation that people come to youtube to remedy

johnbrownell

Ive done induction on this particular problem. I know it as the "Coin problem". They give us the two coin denominations first, then the Frobenius Number which claims they can make n cents out of blah cent coins and blah cent coins for all K greater than or equal to n.

Example: Prove with induction that with 8 cent and 3 cent coins, for all "n" cents greater than or equal to 14 can be paid with 8 and 3 cent coins. I was taught my base case for this will be the trivial case of where n = 14, how it can be paid with 8 and 3 cents i.e 14 = 8a+3b. Not this P(0) as you point out. My hypothesis would be that P(k) is true such that K can be paid in 8 and 3 cent coins where K is greater than or equal to 14 and in the step prove P(K+1) in the step with cases.

For this specific example, My cases would be the following:
Case 1: I have at LEAST FIVE 3-cent coins. I can take out all five 3-cent coins and put in 2 8-cent coins.

Case 2: I have at least FOUR 8-cent coins. I remove all four 8-cent coins and put in 11 3-cent coins.

Case 3: I have at most FOUR 3-cent coins and i have at most THREE 8-cent coins. But in that case, that doesnt get me what I'm trying to prove so that can't happen.

motorheadbanger

When the mouse was over the 8 cents I tried to move my mouse to move it hahaha.

kurchak

I think having an instructor with a clearer and smother voice would be desirable. It is very hard to hear and to follow. Examples and instructions are good though.

albertnoven