Epic Induction - Numberphile
Вставка
- Опубліковано 2 сер 2022
- Featuring Zvezdelina Stankova... Continues with "Question 6" at • The Notorious Question... - More links & stuff in full description below ↓↓↓
Zvezda: math.berkeley.edu/~stankova/
More Zvezda on Numberphile: bit.ly/zvezda_videos
Zvezda on the Numberphile podcast: www.numberphile.com/podcast/z...
A third extra video on induction is on Numberphile2 at: • Induction (extra) - Nu...
Tom Crawford tackles a similar rectangle problem here: • A Problem with Rectang...
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumberphile
We are also supported by Science Sandbox, a Simons Foundation initiative dedicated to engaging everyone with the process of science. www.simonsfoundation.org/outr...
And support from The Akamai Foundation - dedicated to encouraging the next generation of technology innovators and equitable access to STEM education - www.akamai.com/company/corpor...
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Videos by Brady Haran
Patreon: / numberphile
Numberphile T-Shirts and Merch: teespring.com/stores/numberphile
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9 - Наука та технологія
Continues with "Question 6" at ua-cam.com/video/NcaYEaVTA4g/v-deo.html
More Zvezda on Numberphile: bit.ly/zvezda_videos
A third extra video on induction is on Numberphile2 at: ua-cam.com/video/P-NVuOTsetM/v-deo.html
@numberphile It looks like you where confusing squares and rectangles in your diagrams?
@@skilletpan5674 I can prove 2 and 5 easy but 3 would take further investigation!
2 is easy because you can cut the corners to make 1 while leaving 1 in the centre! 1+1=5
"Normally we would call it base case, but B.S. really caught you"
Truly this professor understands education on the deepest level.
A perfect line slipped in there totally deadpan.
And then "Now we are done with the B.S." :-D
Well we use V(0), V(k) and V(k)=>V(k+1) but you can use whatever you want
false.
40 minutes with Zvezda, such a treat! 😃
Didn't realize this was 40 minutes until I've read your comment. Didn't felt like 40 min at all.
Aww, I took Linear Algebra with Professor Stankova and she was my favorite professor at Cal! ❤️ she’d always greet us with “Dobro utro everyone!” which is good morning in Bulgarian.
Calling the base case the "BS" is actually quite appropriate lol. It's typically the least elegant part of the proof and is rarely more interesting than just checking a completely obvious fact.
Can’t build a solid house without a foundation and that requires breaking ground. 🤷🏻♂️.
I think of the bs a bit like the last piece of the puzzle 😌
Mark Rendle entered the chat
Well, there are some cases where the BS is the juice part. For example: the chain rule applied to derivative of n functions multiplied
@@caiollvllal True. I remember in an analysis class doing induction on the difference of the number of terms in two sums, and the base step was really complicated, but the inductive step was completely trivial. To this day I haven’t found it in my old textbook.
"Once you have it *or some annoying classmate gives it to you, pretending they know too much...* "
Now THAT'S a line that could only come from an academic and an educator. I don't know how Brady kept the camera still in that moment, because I was shaking with laughter.
Gimbals are joke-proof.
That statement definitely caught my ear, but I'm a bit lost on what the joke was 🙃 I don't suppose you could explain it to me? To be honest, I think I only understood about half of what was going on here. The most challenging induction proof I ever got through was the sum of 1 to n natural numbers 🧐
@@hamc9477 just a joke about how there are always annoying students in a classroom disrupting the educational moment by blurting out answers that may or may not be helpful. In this case, maybe the teacher asks you to try a textbook problem on your own and the annoying student just looked in the back of the book for the answer but didn’t actually understand.
The delivery of the line was perfect, too.
false.
Hooray for new Zvezda content! My day is made.
Could we have 40mins with Prof. Stankova every week?
Brady, I love this kind of video where Professor Stankova just take us on a journey, going through all the nitty-gritty of the logic and reasoning of a mathematical process.
I love this so much. I'm a seasoned student of math, yes, but seeing induction explained like this is so beautiful.
Yaay, eventually something from prof. Stankova! I really missed you, professor, great to hear you again!
When i hear 'without loss of generality', my prof. always told us to take a moment and think why generality isnt lost, even if its as simple as this case, where you can just relabel the sides, such that the inequality holds.
One of these days, I want a proof to write "WITH loss of generality." Just to screw with everyone.
Mathematical induction is very close to my heart. I used it in my masters thesis for formal argument. It would be very funny to have Zvezda explain how induction can be misused to arrive at wrong conclusions.
"We are done with the B.S."
All I could think was that when brady said "I've just joined the most famous duo in comedy history" that we had a real missed opportunity. If he had joined Abbot and Costello, they could have been A, B and C!
Yeah, as an American I immediately took umbrage at Brady's insinuation that the greatest comedy duo is any other than Abbott and Costello.
This video is amazing. She explain herself so good and has the ability to make ppl like math. If she is a prof im sure her students love her !
* *so well*
@@robertveith6383 🤡🤡🤓🤓
0:22 that last white domino, the one that falls off, *genuinely* seemed to show 1/12. Which is super sweet given that she later claims that that line was meant to for infinite induction.
but in the table, just before that, it says 3/12.
“Oh look, new Numberphile dropped. I’ll check it out” I said to myself.
Oh, interesting topic.
Oh, the video is called Epic Induction.
…
…
This video is 40 minutes long!! What a blessing, Brady.
Gotta say everyone on numberphile are superstars but Zvezda just has a little something extra special about her. Loved the video :D
I so wish I'd had this lady as a tutor in college! Her whole delivery makes you (or at least me) pay attention. Wonderful.
My teacher usually explains induction like this: "I've proven that I can go up one step on a staircase. I've proven that I can go up the first step, and get on the staircase. Therefore, I can go up as many steps as I want."
Love the Brady and Audrey on the moon painting at @5:35!
I think this professor, Matt Parker and James Grime are my favorite recurring guests on this channel. They have such excitement in their explanations.
I like the explanation that induction is about "There is no smallest counterexample". You prove that the smallest possible case can't be a counterexample. And you prove that any successor case can't be a counterexample. And thus there cannot be a counterexample. (Not that induction proofs are necessarily proofs by contradiction.)
I haven't tried to teach it that way yet. So whether it's actually a helpful way to introduce induction remains to be seen.
Also, as for the 2 squares homework: The moment you know 5 is impossible, the existence of the windowing technique immediately rules out 2.
Advantage of this method: With care, you can do induction on any well-ordered set, not just on the (positive) integers. This is a necessary building block for transfinite induction. Also, the well ordering of the positive (or non-negative) integers is, in some sense, "obvious" enough that students can intuitively see that it must be true, whereas induction is often taught as an opaque "magic spell" proof technique.
Disadvantage: If you want to do it rigorously, your inductive step actually has to be "not S_n+1 implies not S_n" (the contrapositive of the usual inductive step), because then any counterexample would create an infinitely descending chain of counterexamples, which is inconsistent with a well ordering of the underlying set. Some students may find this confusing or unintuitive.
The windowing technique doesn't (necessarily) work backwards because there is no way to guarantee the existence of four squares that partition a larger square. Indeed, the construction for even numbers 2*k where there is one large square and 2*k-1 squares arranged along two of its adjacent sides has no four squares that can be combined into a single, larger square.
@@AubreyBarnard Indeed, windowing doesn't work backwards. Which is why the solution for 8 doesn't make 5 possible.
However, if 2 were possible, you could window from there to 5. But 5 is impossible. So 2 must be impossible. That is what I mean when I say the windowing technique together with 5 being impossible immediately yields that 2 is impossible.
Thanks for keeping this channel alive, Brady! I've been watching since high school!
some tactics here for the squares:
the 8 trick as well as the 6 trick are special cases of the generalization where you can cut any square into a square of size N^2 and un-cut a K^2 size section within it. The window technique is also a special case of this. respectively, they are 4^2-3^2+1, 3^2-2^2+1, and 2^2-1^2+1 in size. The change in size produced by these squares is exactly N^2-K^2 = (7, 5, 3) respectively. You can do this with any numbers N and K.
Was not prepared for that cutaway with Brady in a spacesuit
I got a chuckle out of the thought of the editor adding in each of those little 'splat' sounds. Great explanation of induction over various problems!
One of my favourite guests at Numberphile
For me one of the best induction proof is the proof of decomposition of number as a unique product of prime number, amazing result.
Very happy to see a new Stankova video!
We did this in my undergrad math club! This explanation felt very natural, thank you 😌.
Thanks Zvezdelina I learned something new today.
Professor Stankova putting Brady in his place again 😂 Always a delight to behold.
Yay! Zvezda! one of my favourites! :)
We aim to please.
40min video with Zvezdelina, it’s my lucky day, jeez
"So, what do we do with 18 people, Brady? We MARRY THEM OFF in pairs, disregarding their preferences. Just for they sake of mathematics, they'll do it."
Long live the Philosopher King.
Love Zvezda. Glad to see her back!
The maths is great, the theatrical performance is great, it's all great.
I once did an induction proof that was weird, just like the squares problem. I was trying to find for which n does a 4-regular planar graph of size n exist, and I ended up showing it by induction with the base cases n=8, 9, 10, and they had that leapfrog pattern as well.
Absolutely EPIC! Thank you!
It’s always a good day when Numberphile uploads, and it’s always a fantastic day when it features Zvezda
Zvezdelina has the amazing ability to retain my full attention while explaining something in a pace way slower than I need.
I feel like I'm sitting in on a lecture from a greek mathematician 2700 years ago. I know all this, but the rationality being explained by a learned thinker is rearranging my thought processes. 😶👍
I simply love this professor.
OH my God 40 minutes! It'll be a pleasure to watch, definitely
Something I don't often see mentioned...
You can do nested induction. The proposition is assumed true for n. You have to show the n+1 case holds for all m. For example, holds for all m
What a delightful teacher!
Professor Zvezda, I love your lectures and lessons. You have a great talent for making complex topics easy to understand, which is amplified by Brady's videography. Please never stop.
I love how long this video is. Also I want pie.
I love the videos with Zvezdelina Stankova
9:54 I think Dr. Tom Crawford did a video on a similar problem as well, it's one of the (old) Oxford Admissions Questions
Yeah I knew I'd seen it before (still forgot the proof haha)
A 41 min episode from numberphile is ♥️
yay Zvezdelina is back! i love her videos
Gotta dig Z's enthusiasm !
Ooh, a lengthy one. I like these
I first saw the odd pie question in The Art and Craft of Problem Solving, by Paul Zeitz. If you like problems like that, definitely check out that book!
Great host and interesting content!
24:20 "Let's say, a really large *evil* number."
Me: 666?
Zvezda: 2000
Me: Oh.
Zvezda is my favourite Numberphiler.
While I might be missing the point of the video in saying this, I feel like there’s a much easier way to solve the “how many subsets exist in a set of n items”. Each item in a set has a 1 in 2 chance of being in any given subset; either it’s in the subset or it isn’t. Permutation mathematics shows that if there are 2 choices for every item in a set of n items, the amount of ways you can group those items is 2^n.
Yes that would be a non-inductive proof.
Also, I'm definitely being pedantic for saying this, but we don't say there is a "1 in 2 chance" of something happening because you either choose it or don't. You would need information of all subsets and pick a subset uniformly random to talk about chance.
“We are done with the B.S.” 😂
Thumbs up, even before viewing. I recently wondered where you were.
16:20 I found another way to prove that n= 2,3,5 are impossible. One can think of certain "simple" arrangements of squares, where one starts with one square and subsequently divides individual squares into any number of squares 2m+2 for m >= 1. These iterations correspond to making a square smaller to fit m squares on each of two sides and one in the corner (thus adding 2m+1 squares to the original 1). From there, some simple guessing and checking shows that a "non-simple" arrangement is only possible for n >= 7, with the minimal example created by having three 2x2 squares in a triangle and four 1x1 squares to fill the gaps in a 4x4 grid. Since "simple" arrangements, in adding 2m+1 squares at a time to an initial 1, can only yield n = 1,4, and n >= 6, and no "non-simple" arrangement is possible for n < 7, there are no arrangements of squares in squares with n = 2,3,5.
Also, for the odd pies problem, I skipped induction be proving that the graph of people pieing (pying?) each other cannot contain any loops with size n > 2, since any subgroup of people of size n where all people pie another within the subgroup (which is necessary to have a loop) must contain a smallest distance such that both people pie each other, creating a loop of length 2, and disallowing any loops of length n > 2. Since any arrangement with all people being pied must have them all in loops, the total number of people n must be evenly divisible into loops of 2 (i.e., n ≡ 0 mod 2 must be true).
Zvezda has a great sense of humour. It sizzles through in all these little comments she makes. Very entertaining.
i hope that portrait from 5:34 is up on Brady's wall!
I really enjoyed this, but I wish she’d been more formal with the contradictions for 3 and 5. I get the intuition for both, but it still felt hand wavy and based on intuition instead of rigorous.
I realize this was about induction, and for that it was a great explanation!
And wow, what a great teacher. ❤
I love how she is not my instructor yet I am deligently working on my hw
I was not expecting the beautiful art of Brady in Space!
Love the video! Great!
Zvezda is such a joy to listen to, and so enthusiastic about her math. She has a wonderful approach to breaking down topics that might otherwise be very dry and formal :)
the first time i learn induction was like the first time i learn real math, before induction everything was like numbers and arithmetic but induction is truly trying to prove something using logic
I love her all videos.
There is a very nice direct proof for the odd pie fight if I am not mistaken!
It goes like this:
Let n be any integer greater than or equal to 2 and assume there exists no survivor. We want to show n must necessarily be even.
If we draw who pies who, then:
- There is a single arrow pointing away from each person
- There is a single arrow pointing towards each person, since if somebody gets pied more than once, there are not enough pies around to pie everybody!
This means that the picture we have drawn consists of only cycles (series of arrows forming closed loops). All these cycles must be of length 2, which means we have paired everyone up and thus n is even!
Why must the cycles be of length two? Well, assume we have a cycle of length 3 (bigger cycles are similar), where A pies B, B pies C and C pies A. Thus AB
The odd pie fight animation gave me Josephus Problem vibes!
If we place each pie-thrower beyond each other's cosmic horizon, then everyone survives.
Finally there will be an IMO 1988 Problem 6 solution without Vieta Jumping! I'm really excited cuz the official solution also wasn't induction, which means that it's her original unique solution!
amazing, how in videos such as these even . . .
On the odd pie fight, if the _different distance rule_ should be respected, could you sort the people in a straight line, with the least distance from each other to the left and farthest distance to the right, and if there is only one end to the right does it mean there should be a survivor? Maybe I'm wrong to think this.
Example line if a < b < c:
L - a - H - b - B - c - L
it loops but since c > a, second L can be ignored, therefore B survives in this case. Are there counterexamples to this method?
The point is not to find a single configuration with a survivor. The point is to prove there is *no* configuration *without* a survivor
It's a simple loop when n=3. Not necessarily a simple loop when n>3. So if you want to think of it in that way, you have to be more precise about what you mean about "distance from each other." For example, if n=15, which of the 14 distances to "each other" is the one that counts, for a given vertex?
5:27 I love the little people.
Very Interesting!
Thanks!
Maybe the best professor on numberphile
¡Gracias!
Thanks Brady!
In Peano arithmetic induction is the last axiom. So it's not provable from the other axioms but just assumed to be true.
great!!
Some watch Netflix. I prefer 40 minutes of zvezda!
The squares problem is very similar to the rectangle problem with Tom Crawford.
I’ve spent a lot of free time trying to prove the collatz conjecture by induction. If I can prove that any number N is guaranteed to eventually reach a number less than N, and every number less than N has already been proven, then N goes to 1. So it shifts the problem to proving that N eventually goes to less than N. If N is even, we’re done. N/2 (3N+1)/2. That is still greater than N, but half of all even numbers can be divided by 4. So 3N+1 has a 50% chance of being divisible by 4, which means (3N+1)/2 is another even number and we divide by 2 again.
(3N+1)/41
This means that all even numbers, and half of all odd numbers must go to a number less than itself. That still leaves a fourth of all numbers that don’t go to a number less than itself within 3 steps.
Let’s assume that we did prove that all numbers eventually go to a number less than itself. Starting at n=1, we prove by induction that all numbers go to 1. N=2 goes to 1, we’ve “proven” that N=3 will eventually go down to either 1 or 2 (the only options) and both of those go to 1. N=4 works because everything less than 4 goes to one and we’ve “proven” everything less than 4 goes to 1. Going step by step, we prove any number N by proving every number less than N works, and N must go to a point less than N. If N eventually reaches a number that we’ve already proven goes to 1, then N will follow the same path and go to 1. So if we can prove that every number N must eventually reach a number x
these 25% are the cases, where the real troubles start
Gracias.😉👍🏾
Awesome!
I now want Prof. Stankova to explain Löb's Theorem
"I'm not gonna argue about Pluto, don't even ask me!"
Lol she's my favorite
Case N = 2: if it were possible, then, by the window technique, also the case N = 2+3 = 5 would be possible, which we already proved is not possible.
Zvezda's handwriting is so satisfying. My handwriting on the other hand 😭
Muchas bendiciones
4:09 when someone finishes giving excuses.
Now for extra points prove that the axiom of induction is valid!
I'm a bit confused on the squares problem. Isn't it easier to go forwards? ie. We have the base cases 6, 7 and 8, which cover all integer classes mod 3. We can also easily prove that if S_n is true, S_(n+3) must also be true, using the window technique. Doesn't that cover all integers?
Edit: I just had a thought - what guarantees that this result is valid? For example, with the 2000 square solution (1000 little squares on two borders) there is no way to 'undo' a window technique, meaning there is no way to generate the 1997 solution.
The 1997 solution is generated from the 1994 solution (with 997 little squares along the borders) by using the window technique.
The 1997 solution is taken as truth by strong induction.