Hi. In the previous video we saw a proof by mathematical induction which seemed to be correct until it actually turned I was wrong. And in this video, we'll consider a few more flawed proofs based on induction so that you can get a sense of how you can make a mistake when you apply induction, and you can avoid it in your own proofs. So we'll consider a few problems and we'll illustrate that although induction is a very powerful method, as any power you should apply it with care. And you'll see that often proofs by induction only seem to be correct while they're actually faulty. And the first problem is the following theorem. We want to prove that for any number of people, for any n which is at least one, if we get n people, all of them are of the same age. Actually it is obviously a theorem which is wrong because we know that people can be of different ages. But now we're going to prove it to using with medical induction. And to prove something by induction as we know, we have to just prove base and step. Base for a n equals one, is obviously true because we have just one person. That is of the same age as the same person so the induction blase is true. Now we want to prove the induction step from n to n+1. By the assumption of induction, for any n people they are of the same age. And so in particular if we take these n+1 people and we arrange them in a row, and take the first n people, those are definitely of the same age. Also by the same n assumption of induction, the last n people in the row are also the same age. So we have first n people of the same age and last n people of the same age. Then we have n-1 people in the middle which are of the same age, with the first n and with the last n. And then it means that actually all the n+1 people are of the same age as the middle n-1 people. So all n+1 people are also of the same age. And so we have proven the induction step and have both induction base and induction steps so we can prove that for one person is also always of the same age for two persons, they are always of the same age and so on. So we have proven our theorem. Now from the other hand we know that the theorem is not true and we know a lot of people of different ages. So what is actually wrong is there something in this proof. Can you spot it? Can you spot what was wrong in this particular proof? Well, it turns out that the induction step was wrong. It wasn't wrong at all. It just breaks for one particular case when n=1 and we move from one n+1 is equal to two. Indeed, let's go through this induction step. If we have n+1 people, which is equal to two in this case and indeed the first person is of the same age with the same person. And the last person is also of the same age by the assumption of induction. But these two people can actually be of different ages because the middle n-1 people which we use to prove that the left part and the right part are all of the same age, these n-1 people are actually zero people. So there are no common people between the left n people and the right n people. When I showed you the proof I showed you like this: n people to the left, n people to the right. Here is the intersection. All these people are of the same age. This person is of the same age with them. This person is of the same age with them. But for n=1 there is no intersection. There's just one person on the left, one person right and no people in the middle which could help us to prove the theorem. This is where this prove breaks. So you have to be really careful when you inspect induction steps. Now let's consider another theorem. That for any non-negative integer n, five times n is equal to zero. Now this is also obviously incorrect, because we know that if we take some number like 10 and multiply it by five we won't get zero. We'll 50. So this theorem can't be true but who are going to prove it now with mechanical induction. To do that we first prove the induction base for n=0 and obviously for n=0 zero, five times n is the same as five times zero which is equal to zero. So induction base is indeed true. Now we're going to prove the induction step from n to n+1. And to do that we will use the complete induction. So assume that for all values from one to n, it is true that 5 times n is zero. And now we want to prove it for n+1. So we'll write n+1 as sum of I and J, where I and J are non-negative integers up to n. So we can just somehow make this number divided into sum of two numbers which are smaller and which are also non-negative. And if they're smaller and then they're not bigger than n and so for them the assumption of the complete induction is true. And then we see that five times n+1 is the same as five times I+J. And we can open the brackets and we will get five I plus five J. And we know that I and J are non-negative integers up to n so the assumption of the induction holds for them. And so five I's equal to zero and five J's equal to zero and zero plus zero is equal to zero. And so we have just proven the induction step and we have both induction base and induction step and so our theorem is proven. Now can you spot what was wrong in this proof? Well it turns out again that the induction step was wrong. And it is wrong not always but it is wrong exactly for one particular case when we move from n equals zero to n+1 equal to one. Indeed, we want to represent n+1 as a sum I equals J of two non-negative integers up to n where n is zero. So I and J should be non-negative and up to zero. But there is only one non-negative integer up to zero it is zero. And so both I and J would have to be zero. But then zero plus is zero. And it is not equal to n+1. n+1 is one and zero plus zero is zero. So it is actually not possible to break this n+1 number into I+J where I and J are up to n. It would be possible for bigger values of n, but the induction step already breaks at the set from zero to one, so it is not important whether we can make a step from one to two from two to three and so on, because already the statement is wrong for n equal one, because we can prove this induction step. And actually if we take n=1 then five times n is five and is not zero. So we cannot actually make this step because we cannot represent n+1 as a sum of I+J, but because it is actually not true. And this was another example of flawed induction proofs. So what you should take away from here is not that mathematical induction is a bad thing and you shouldn't use it. It is actually that you should be very careful when you're proving your induction steps. Usually the induction base is kind obvious; you just need to prove something for a particular value of n and you typically prove it by hand and it is more or less obvious. But when you're proving the induction step you should really check that your assumptions can be true. That you can use the statement that n-1 middle people are of the same age or that n+1 can be divided into two summons which are non-negative n up to n and things like that. So you should check that you don't use the assumption from induction for n-3 when n should be non-negative, and n is less than three. So there are many many ways how you can spoil your proof and you have to be careful in this proofs of induction steps. And maybe you should test those proofs with a few small values of n, just to make sure they're correct. You only need in theory to prove a base case for the smallest value of n or if you're using complete induction maybe for several. But to be sure that your proof goes well you could also try to check it for particular small values of n and see that it goes through.
