a * b = ab + a + b

welcome to another video this is a Harvard MIT math tournament problem I do not remember how I got this problem if I found it or someone sent it to me a while ago and I wrote it down or it's one of those things that I received from the many subscribers who have emailed me problems but I know that I was working on it on my tablet and I just saw it again and this is an exciting one we have a a star B is defined as a b + A + B we need to evaluate one star open parenthesis to Star all the way to 100 and the way this is written if we're going to apply our pmas it means we're going to start from 99 star 100 and we're going to go to 98 star the answer we got the 97 times the answer we got until we get to one times the biggest number we're going to get so what we're going to do is most likely start from the middle and see if it works let's get into the [Music] video so let's start with 99 star 100 and see where it takes us so we're going to apply the rule here it's going to be equal to 99 * 100 + 99 + 100 what do we get we're going to get 99,900 plus this is going to be 199 so if we add these two together we're going to get 10,000 and 99 okay so that is the innermost answer that's this one so we're going to go in and try to do 98 so we're going here now 9 * a star this answer so it's 98 star this answer it's going to be equal to 10 99 okay so the first thing we're going to do is multiply 98 by this right here you can see that you have to stop you're not expected to do this computation 100 times because that's what's going to happen okay or maybe 99 times okay because that's what's going to happen and the numbers were going to are going to get bigger and get crazier quickly I don't even know how to do this because by the time I multiply the board will be filled with all kinds of multiplication so you want to go back again and think why did they say I must start from the innermost what if I start from the small numbers but that's going to break the rules of pmas because because you have to do the parenthesis first but there are times where doing what's in the parenthesis first does not matter you can change the position of the parenthesis and that's what we call the associative property of any operation right if I say 1 + 2 + 3 penda says I must do this first so I'm going to get 1 + 5 = 6 but if I know that this operation of addition has the associative property I can change the position and write it this way so I start from the smaller number I don't have to get the big number first you see that so this is going to be three + 3 and that gives me six the same answer so the only question we're going to ask now is does this operation have the associative property can we change the position of the parenthesis so that it is first one star two and then we can start adding three like that well we got to prove it is star associative okay if it is associative it's going to follow the rule that says that a star B Star c will be equal to a star if we do the parenthesis let me do this first on the side so let's do this so this is going to be a star what is B Star C it follows this definition it's going to be the product of the two then the sum of this and this so it's going to be a star um b c plus b + C that's the definition of b star C based on this operation now what is a star is the same thing it's going to be the product plus a plus this like that so now I can distribute and I'm going to get a b c plus a B plus a c plus a plus b c plus b plus C if I rearrange I'm going to have a b c then I have a AC BC so I can have plus AB plus a plus b c + A + B + C so my focus now is I know there's something like this and I have this and I have this so those are the three parts okay so what I'm going to do now is instead of putting the parenthesis here I'm going to put it here we have a star B Star C let's see if we're going to get the same answer as this if we get the same answer it means the associative property exists for Star okay and we're going to use it and I'm not going to start from 99 to 100 I'm going to start from 1 to two and the reason we want to do that is small numbers are easy to Monitor and you can see the pattern that is building and then you can say I have seen the future like that so here we go so the based on the definition it's basically this so we're going to have a B plus b plus c star C okay now when you distribute you're going to have no when you do this operation again it's going to be this times this which is going to be a + b plus something is wrong ab+ A plus b come on A+ B okay I was looking at c² I said no that ain't going to happen time C plus plus the first term a + a + b plus the other one which is C so let's simplify this is going to be a b c + a C + B C + a b + A + B plus C it looks like we've gotten the same answer as what we have there because this ABC is here AB plus AC plus BC is here and then the third part is also Al here so based on this this guy and this guy are the same which means by the associative property the associative property of star we can rewrite this let me say let this be Q let's call this Q okay so I don't have to write the entire thing it means Q since star is associative asso ah I can't spell anymore since star is associative Q can be written as one star two star you see what's going to happen now so instead of us putting the star on the right the parenthesis is now facing this direction so we're going to have star three star we do this first it took me a while to figure out the number of parentheses I had to put on either side okay but that's what I mean okay the parentheses will now build on the left hand side you start from this then you go to three then you go to four instead of us going in the opposite direction because of the associated property now something usually happens when you start multiplying numbers together it is a commutative property which means that sometimes a b is not the same thing as ba a like B Star a is not the same thing as a star B but I can see already that this would have the commutative property but in order to not because at this point I can see where it's going to be relevant but commutativity is very essential when you're doing addition and multiplication and I probably may have used it and not realized it cuz when you it's like matrices when you multiply from the left you cannot get the same answer as when you multiply from the right with by another Matrix so that might be the case so it's just generally good for you to check for commutativity so this is what I'm going to say um um check for commutativity okay so which means I'm going to say a star b a star B is going to be AB plus a plus b right that's the definition and this can be written as B A + B + a which is B Star a so it is obvious I just Chang because this is a real number the product of two real numbers when you multiply you can easily switch them you get the same answer so that's what I did and for addition you can switch addition also so if you do that you can see B * a is the same thing as a * B so this is just for safety reasons cuz I may have used it and not realize that I've used it I don't think I have actually but you never know okay so now so let's go back now and begin to solve this problem because the hardest work we're supposed to do is what I have shown here this claim about associativity so now here let's begin what is one star two let's just do maybe two three or four iterations of this computation and you going to see a pattern it's that pattern you're going to use to predict the future when you get to 100 observe observe that 1 star 2 is the same thing as 1 * 2 + 1 + 2 and that gives you 2 + 1 that gives you 5 you go to the next one so now the next answer we need is going to be five star three so 5 Star 3 is going to be 5 * 3 + 5 + 3 see what your answer is going to be it's going to be 15 + 5 20 + 3 that's 23 okay now you may not see a pattern yet but you're going to see after a while let's do the the next one this is now going to be 23 star 4 you you notice that this number is two this is three and this is four right okay now pay attention to the answers we're getting 23 St 4 is going to be 23 * 4 + 23 + 4 23 * 4 is going to be 92 92 + 4 is going to be 96 96 + 3 is going to be 97 97 no 99 rather and 99 + 20 is going to be 10 19 now I'm going to stop here because I have enough evidence to make a claim which I'll still have to prove just as we proves this one look this is five when it was one star two this is 23 when it was five star three the answer here appears to be having something to do with this guy or to have something to do with this guy so 5 is actually 6 - 1 and 6 is 3 factorial so this number is one less than the next this number here factorial this number is 23 but four factorial is 24 so this number is one less than four factorial this number is one less than 5 factorial which is 120 so we can say from here that let's say you have some value B which is what you get from the beginning star any number n your answer + one you add one which is the next line factorial minus one is going to be your answer so this is my claim it is that if we start from one and we do one star two and we then do star three and we continue like that and we do star we go on until we get to n what we're going to get is base basically n + 1 factorial - 1 because then what's the only thing you need to know is where you're stopping n so if we're going to be stopping at 100 our final answer is going to be 100 + 1 which is 101 factorial minus one and that's it you saw how big those numbers got yes that's what it's going to lead us to so how do you show that this is true mathematical induction is what what we're going to do because I don't I don't have any other strategy for this one for n = 2 we're going to have 1 star two must be equal to this claim 2 + 1 factorial - 1 this is going to be 3 factorial which is 6 - 1 which is 5 and clearly we got five so the base case is true now you can try a second case just but we already have the cas is listed out here so don't waste your time time trying to do the second case just move on to the Assumption so assume we're going to assume that one star two star 3 star all the way to let's say k is equal to k + 1 factorial -1 so what do we want to do next if this is true we want to show that it is true for the next number see the next number is going to be k + 1 then this will have to change to k + 2 because you this is always one more than this one so we're going to say for for k + 1 for n = k + 1 true um this is for actually for n = k so now we're going to do for n = k + 1 what do you think is going to happen well we're going to have the same pattern it's going to be one star two I hope I'll have enough space I going have to come back up here it's going to be one star two star three star all the way to K star k + 1 yeah that's how it works what we're saying that this is going to be equal to see what this is going to be equal to what did we say this was again look at this part we said this part is true that whenever you have something like this if it stops at k then your answer is going to be k + 1 factorial minus one so it's going to be k + 1 fact iial minus1 star so all of this star k + 1 so this is the math that we need to Now work on okay if what we have here can simplify to k + 2 factorial because it's the number after k + 1 if we get so what we're aiming to get here is k + 2 factorial -1 if this becomes this then we're good then the claim that the answer is going to be 100 + 1 factorial - 1 is correct I'm going to pull this equal sign all the way to the beginning here okay so now this is equal to if we do the perform this operation based on the definition of star it's going to be the product of these two plus this plus this k + 1 factorial so I multiply these two okay minus k + 1 then the second part is we need to add this plus k + 1 factorial - 1 so I just added this part now I need to add this part plus k + 1 beautiful let's simplify whatever needs to be simplified I know that this minus1 will take out this minus1 so what I have left is just K if I distribute this parentheses I'm going to have minus K -1 in fact I think I should do it now okay everything looks juicy all right so minus K will take out minus K minus1 will take out this + one so all that is left is just minus one now I have this and this so I can factor out k + 1 factorial if I factor out k + 1 factorial I'm going to get k + 1 factorial left behind will be k + 1 and I'm going to get a one here from here + one in parenthesis so I factored out k+ one from these two terms I got k + one and I have a one left here and then I have minus1 do you notice that this k + 1 + 1 is k + 2 right so this is equal to k + 2 * k + 1 factorial -1 k + 2 * k + 1 factorial -1 but k + 2 * k + 1 factorial is k + 2 factorial this is equal to k + 2 factorial minus1 and this we have proven that this claim is correct claim is true by mathematical induction okay I can't write the whole thing now we can write our conclusion therefore Q which is this original problem is equal Al to 10 And1 factorial minus one this is our final answer that looks weird let me put this in parenthesis everything looks like a one minus one okay this is a better way to write it and that's it never stop learning cuz those who stop learning stop living bye-bye