The Magic of Induction – Numberphile

so today I want to talk to you about induction a lot of people see this as kind of a magic and why does it even work so let’s start with the example you know something very very classic so 1 is just 1 1 + 2 is 3 1 + 2 + 3 is 6 1 + 2 + 3 + 4 is 10 can continue this or maybe you know the formula that 1 + all the way up to n = n² + n / 2 so if n = 1 we’re just summing 1 that’s 1 + 1 / 2 that’s fine if n = 2 we have 4 + 2 that’s 6 / 2 that’s 3 if we have n = 3 this is 9 + 3 that’s 12 / 2 6 so how can we prove that this is always the case classic example perhaps one of the few uh uh canonical examples of proof by induction so how do you do this you say well this is my conjecture and I’m going to prove it like this I’m going to say base case right the induction base we prove this for Nal 1 so for n equal 1 I’m just going to verify by hand so for Nal 1 we have 1 is 1^ 2 + 1 / two that’s two / by two that’s one we already had this discussion over there excellent so now you know if you’re in high school maybe this is how you were taught uh you write down the induction hypothesis and when I was in school we were taught you have to write it like this uh cuz this is the magic they don’t explain why it works they just tell you what to write to get the marks so the induction hypothesis is that this thing is true for n so the induction hypothesis is that this sum up to n where n is some given number equals that and now the induction step we’re going to assume the hypothesis and prove this for n + one so now we want to sum all the way up to n + one so what what is this this is all the summation up to n and then again this one extra bit of term the hypothesis I have made is that this bit equals to that cuz this is what we assume so we can replace these two terms so this equal n² + n / 2 and I still have this n + 1 so this becomes n² + n + 2 n + 2 / 2 which becomes com n² + 3 n + 2 / 2 and well I know the answer to this because we know what we’re trying to prove but you can verify that this is indeed n + 1 squar + n + 1 / 2 one way to do this is to open the parenthesis here and sum all of this and you can check that we can do that so now we said okay so we have proved that the sum up to n + one also has the same form as this right instead of n we have n + one the conclusion is that the identity hold for all natural n that’s a conclusion that’s how we prove that this is always true because it always works for the next one exactly so what’s the idea here it’s exactly what you said I’m starting at one and then I’m going to keep going one step at a time and and somehow by just proving these two things I managed to prove infinitely many things there are infinitely many natural numbers right if you now say I’m going to plug five billion into this then instead of summing all of this you know there just the small formula right the the General open Legend with um don’t have the reference of the top of my head but I’m pretty sure it’s the buunk uh it’s that gaus when he was like five or seven or something his school teacher told the kids oh sum all the numbers from one to 100 and he came up with this formula and finished like that uh fairly sure this is Thoroughly debunked we’ve set our number five but all right well you know there’s a half lifee for factoids um tell me why you said induction is magical so this is kind of clear let’s do something where it’s not at all clear let’s prove that every natural number greater than one has a prime divisor so naturally you want to prove this for all the natural numbers so I’m going to say well um let’s do it by induction let’s for one there’s nothing to check for one cuz we excluded it you know purposefully also for zero again excluded purposefully so we can check it for two can check it for three can check it for four and so on and so on but now if you look at what we just did with the base and the step if I tell you that five has a prime divisor which is five how is this going to help you find what prime divides six right we know what prime divides it’s two and three but the only hypothesis you’ve had is that five has a prime divisor so what do we do now well now we turn to something that that’s called strong induction or complete induction which has a much um much more mindboggling kind of hypothesis so if n is greater than one then n has a prime divisor this is what we want to show so my induction hypothesis now strong induction I’m going to call it is going to be if every K less than n has a Prime divisor n has a prime divisor so I’m not just assuming in the case of six five and six I’m not just assuming five has a prime divisor I’m saying 2 three four and five have Prime divisors let me show that six has one so the proof kind of silly at this point so this is the induction step so I’m assuming this up to n whatever n was and I have two cases now case one maybe N is a number if it’s a prime number it divides itself we’re done right then as mathematicians like to say trivially n has a prime divisor by definition almost by definition exactly this is the point of trivially right what happen if it’s not a prime number so in this case by the virtue of it not being Prime there are let’s say K and M such that k * m = n in the case of six this would be 2 * 3 right does it have to be two numbers like do we already know that it can only be built from two numbers well it can be from any any numbers but you can group them together into two bits the important thing is because n is not prime it’s not only that there are two numbers I’m also in the position to require and both K and M are smaller than n because if n was prime one of those had to be one and the other had to be n but because n is not prime that means exactly I can find two smaller numbers whose product is n now look at the uh induction hypothesis so all the numbers before exactly in particular K which is a smaller number so the is a prime P which divides K right so k equals P * K Prime but that means n is M * K which is M * K Prime * P so now p is a divisor of n so we found a prime divisor now a lot of people struggle with this because you’ve been thought about induction you start with a base case and you keep working upwards there was no base case there was a secret base case every time you see induction and for that matter every time you see recursion there is a concept called well-foundedness which is lurking in the background and the idea of well-foundedness in a nutshell is that you have some kind of ordering that relates objects numbers functions whatever and whenever you look at a collection of them there’s a smallest one so but smallest one in that order this is important all right so the natural numbers this is the defining property if I tell you all the numbers you know between a 100 and a thousand which are prime numbers there’s a smallest prime number in that collection right we know there is one at least and you know why do we know that’s a different story but we know there’s one and so there’s a smallest one right if I tell you uh the power the smallest power of two between a billion and a Google Plex we know there’s a smallest number of two this is exactly this whenever you have induction especially these kind of complete inductions there’s some kind of a relation hiding which is well founded in the case of uh Prime division what we have is the divisibility relation so let’s say that n divides M this is the notation now on the natural numbers if you look at the natural numbers it’s very easy to show that there’s a smallest one in any non-empty collection according to this relation because it kind of connects with the standard ordering of the natural number but the secret is the smallest objects here in this relation are the prime numbers CU they have nothing below them except themselves and so this induction is really saying look at this division relation so we have uh let’s vaguely draw how it looks like we have one which is at the very bottom and we’re going to ignore that for now because we only look at things which are greater than one above one we have all the prime two and three and five and seven and 37 and whatever and now you have four which is this and six and 9 and 10 and 25 and uh 15 here you know all all of those things 24 and all it it gives you this kind of relation and what you’re doing here is saying look at the base case the base case this one part is all the prime numbers this is trivially true and then when you continue upwards if you look down from 24 it has e Prime divisor below it this is the whole point of being well founded you look at all the divisors there’s a smallest one and this is exactly being Prime so this could be argued that this proof really checks that this relation is well founded on the natural number numbers or the other way around that if you have proved that this relation is well founded on the natural numbers which you can in other ways you have proved that every number has a prime divisor you see there’s a lot of examples of induction and recursion and they all work on this for example uh if you don’t mind me going a little bit into programming uh let’s talk about the factorial argument so how do you compute the factorial of three 3 factorial is 1 * 2 * 3 that happened to be six and 4 factorial is 1 * 2 * 3 * 4 which is 24 and n + 1 factorial is n factorial * n + 1 in general uh let’s say you want to write a python code you know to to program for this the natural thing is to just have some kind of recursive thing you start by saying okay if n equals 1 returns one otherwise call the function with the previous number the runtime on this is fairly easy to compute it’s end steps right let’s say you want to put a thousand factorial and you haven’t done any adjustments to your software settings or whatnot uh python will throw an error because it has a stack limit of a th so if it goes a th functions in it says this is too much I can’t do this anymore let’s define a different recursive function instead of saying just compute the last one look at the whole interval from 1 to n and then say split it in the middle right with whatever if it’s an odd number either way if and take the product of this entire interval so if this is just one number it’s just the one number otherwise you multiply what do you do you split this one in half and you take these two and you split this one in half and take these two and you keep splitting this gives you kind of a binary search what you end up with is that uh let’s say we wanted to compute you know uh 24 factorial this is pretty big I’m not going to even remotely try to do this but it first does 1 to 12 and 13 to 24 and then here it says oh I want to compute the product of all of these numbers I’m going to do 1 to six and 7 to 12 and here I’m going to do 1 to 3 and 4 to six and then one to two and just three and now three is just itself and this is split into one and two and then you take the computation of those two and you put it here and this is just the one thing so you go back up here again this is pled into 4 * 5 and six and then four and five and you start going back and what you do is you go down in the tree and you start going back up and and you know Computing over the branches at no point in this three of of recursion you’ve been more than 1 2 3 4 five steps deep much better than 24 steps deep if you compute how it looks like if you take a thousand you’re going to find out that you’re only something like 10 steps deep the the use is so much better of of time and space but what we’re doing here is we’re looking at the binary tree and we’re saying well this tree is well founded because it’s finite it has to be so we can do recursion on the tree this is the structure where you define the recursion on just like in the proof with the prime numbers we actually had some secret structure where we did the induction on that and if you think about all of the induction arguments as being there’s some structure there and it’s doing something to make it E easier or harder and maybe I can take a different structure that allows you to come up with new and inventive algorithms and induction arguments in all manner of places in mathematics and programming and whatnot and uh it took me so many years to really get to the bottom of this and this is so amazing and when you talk to other mathematicians you know poof my induction is kind of magic just do the one you do the step you get everything how does that happen this is how it happens it’s about well-foundedness doing induction or not