[MUSIC] Hello everybody, at the end of last time, we saw that we need a deeper understanding of the bionoiminal coefficient. N choose k, if we want to obtain compact nice formulas for certain sums and count more sophisticated objects. So this time, we start the battle against the binomial coefficient, let's try to see, let's see how far we get. So the first thing, I want to show you by the binomial coefficient, it satisfies this nice recurrence. So this fact actually have two proves, one is just by pure calculation and one is more about thinking about what n choose k means. So let me give you the proof by calculation first. So remember, we have a formula for the binomial coefficient, which is n factorial divided by k factorial times n minus k factorial. And now we can just plug in the formula into our recurrent appearance to see whether it works out. So let's try to do that, so what is n-1 choose k + n-1 choose k-1. Okay, let's just plug in the formula that we have. This is n-1 factorial divided by k factorial, and here, we get n-1-k factorial. And here we get n-1 factorial, and here, we get k-1 factorial and n-k factorial. Okay, let's put the fraction together, so what is the common denominator, the common denominator is k factorial n-k factorial which is already quite good. And the first term, we have to multiply by, so this we have to multiply it by the term that's basically missing down here. Yeah, which term is missing down here, that is n-k, and here,in the right term, the factor that is missing down here is factor of k. So this is times k, and now you see we can factor out the n-1 and get n-k+k divided by this And now this is of course, This n and then this together is the n factorial. So we're done because this is again the formula for n choose k, but this just a proof of your calculation. It's not very inspiring, let me show you a little bit more inspiring proof that actually tells you why this recurrent formula is true. So let this be our set of size n and let's take an element x in the set. Now if you want, if we select the subset of size k, this is a subset x of size k. There are two possibilities. First, we include this element x in our set, and we select k-1 additional elements from the rest. And for this, how many chances do we have? Well n-1 choose k-1, right? Because there's n-1 elements left, and we have to take k-1 from them, or we could choose to not include x. But then have to select, We have to select k elements from the rest. I mean from the set without x, so for this now we have n-1 elements left, and we have to select k of them. So the total number of choices is just this plus this, all right? So together, it gives the full number of choices which we have seen as n choose k, right? This is a more intuitive proof of the recurrent formula. All right, so here is a nice thing kind of a fun thing you can do with a formula. So let me write, for example, 3 to 0, 3 to 1 and so on, in one row. What it basically tells you, for choose 2 is simply the sum of these guys upstairs. And 4 to the 4, I mean, technically would be the sum of this, but what do we have here? Well here technically, we have 3 choose 4, but this is of course 0, because you cannot select 4 elements, right? There are not enough elements around. So we can, okay, kind of this, and I mean if you do that so let's fill in the numbers. You see, kind of the first row, we have here is 1 3 3 1, and then the next would be like this. And of course, I mean this row also comes from something. So actually, we can start like this. This would be 0 choose 0, and then this would be 1 choose 0, and so on. And we get the next row by just adding up the two neighbors upstairs. And it goes on like this like 15 20 15 6 1, and let's do one more. Okay, my computer is bugging me about some whatever, some Wi-Fi or something, no idea what. All right, so we get a kind of triangle, where the nth row at the kth position has a binomial coefficient n choose k. And this has a name, it's called Pascal's triangle. And a fun thing happens, if you take Pascal's triangle module two. So you're only looking at which numbers are odd and which are even. So let's mark all the odd numbers, so these are odd, this is odd, and then this is odd, and here this is odd, this is odd, this odd. So we get kind of a certain structure, and if use a computer to plot this, or you simply to go Wikipedia and look at the figure, you get this kind of nice fractal like object which is called Sierpinski triangle. Now this is called Sierpinski triangle. So let me write this, this is basically n choose k modular 2. Another important thing with a binomial coefficient appears as the following formula. So in high school, you might have learned the following formula x + y squared is x squared + 2xy + y squared. And maybe you even remember the formula for this. Anyway, but today we will see a formula for general n, which is the following. It's called the binomial theorem x + y to the n is this complicated sum, and let me explain it a little bit. So here, this is an expression with two variables. This is called a binomial and this is it's coefficient, right? In this expression, and therefore it's named binomial coefficient there is where the name actually comes from. So again, I want to show you to proof of the theorem. First one with a lot of calculation, and then approve with just thinking. Here's the first proof. Use induction on n. Our base case is that n = 0 in which case x + y to the 0 is 1. And the right hand side would be the sum from 0 to 0, 0 choose k, x to the ky to the 0-k. You can easily check this, it's also 1. So for the step, we suppose the formula is correct for n, and we have to prove it for n + 1. So what is x + y to the n + 1? Well one thing that is easy to see, it's x + y times x + y to the n. So now by induction, we can plug in the formula for x + y to the n, because we can assume by induction that the binomial theorem is true. Here's a little trick to make things a little bit easier. In this sum, we sum up from k = 0 to n, but actually, you can convince yourself, we can actually sum up of all values k, of all integers k. Because if k is not in this range, for example, is k is negative or larger than 0, then n choose k is, if you look into the definition anyway 0. So by just letting k run over all integers, we just add a bunch of zeroes. So we don't change the sum, but it makes the proof a little bit easier. Okay, so we use the induction hypothesis and see that this is x + y times n choose k, x to the k and y to the n-k. And now we can expand this product, we get x times the sum plus y to the sum, so we get now two sums. The first sum, we multiply by x, so we get k + 1 up here, and the second sum we multiply by y. So, x to the k, y to the n+1-k. And now we do some little trick that's called a change of variable. We say, hey, look in this sum, we renamed k + 1 to bj. And if we do that, then we get over here the sum of all j, now you have to think what is k? Well k is j-1, and then now we get x to the jy, and now you have to think what is n-k? Well n-k turns out to be n+1-j, and here, we simply get the same sum. And now you see the change of variable, because we set to k ranges over the whole integers. Now we set j to be k + 1, it also ranges over the whole integers. So we don't need to keep track from where to where the variable runs. And this makes the change of variable a little bit easier, we just have to think less. And now you see, this term here, it's the same as here. So now we can pull the two sums together, and we actually get the sum over all k, x to the k, y to the n+1-k times the sum of these two things times. Let's see whether I have enough space, n choose j-1 + k-1, now change the name back n choose k. And by our recurrence formula, we know that this is simply n + 1 choose k. All right, so this is the inductive proof of this theorem. Now that would be the last thing for today. I want to show you the kind of more intuitive proof of this theorem. So x + y to the n equals, and you can just write it out. If you think about it, this is a sum of 2 to the n terms, right? If you multiply it out for every combination you get a sum of, so you get 2 to the n total. And when do we get like x to the k time y to n-k? Well when we select, x in k out of on all n (x + y), and there are n choose k ways to select that. And therefore, the coefficient of x to the k times y to the n-k is exactly the binomial coefficient n choose k. All right, that's it for today, thanks. [MUSIC]
