[MUSIC] Hello, everybody. Today we continue our battle against the binomial coefficient or to put it in less belligerent terms, we try to understand as much as possible about it. So I want to show you some surprising identities involving the binomial coefficient. So for example, what do you think? Can we find a nice expression for the sum? Yes, we can, but that's not the point. The point is I want to show you a method, an abstract method, how to come up with formulas for such more or less involved sums. So, we have the formula, our goal is to find a more compact expression for it, and the way we do that is we start by finding a combinatorial interpretation of what we have. And here's our combinatorial explanation, suppose we have a parliament of size n, and within the parliament, we want to select a committee. Now let's say the committee has size k and the committee needs a speaker who's also a member in the committee. So, how many choices do we have to do that? Well, you see, to choose the committee of size k, we have exactly n choose k choices. And once we have chosen the committee, we have k choices to select the speaker. Now, that if I don't restrict the size of the committee and it can say, well, it can be whatever. Just must have a speaker, then in order to get the number of possibilities, I have to sum up overall values of k. So, this is our interpretation of this sum. We have a parliament of size n, you select the committee, and once you have the committee, you select the speaker. All right, so now, we can actually write it down in a more compact form by inverting our selection of committee and speaker. So again, we have a parliament of size n, but now what we do is, we select the speaker first. So we have n choices to select the speaker. And once we have selected the speaker, we have to select the committee. And in order to select the committee, we have to decide for each member of parliament whether we put them into the committee or not. So, we have two choices for each member of the parliament, except for the speaker. For the speaker, we have only one choice. Here, she must be in the committee, okay? So, we have n minus 1. We have to make n minus 1 choices, so the total number of combinations is 2 to the n minus 1, times n. All right, so you see how we derived an elegant formula for this unreal sum. Now, let's see how far we can push this approach. Can we use it to compute a nice formula for this sum? So let's try again. Okay, let's try this. We have a parliament of size n. We select the committee. And the committee might have size k. So this n choose k. And then, well, k squared, what is a combinatorial explanation for k squared? Well, we could say, the committee needs a speaker and a chairman. And they could be the same person, so we have k squared choices. So that's a combinatorial interpretation of the sum. So to do it, so now, let's again invert it. Let's say first, we select chairman and speaker. Speaker. So for this, we have an n squared choices. And then, let's select the committee, but the committee must contain both the speaker and the chairman. So how many choices do we have? Well, we have a choice to include or not include each member of parliament except chairman and speaker. All right, so what we have just done is we have derived a wrong formula. We can easily take the formula that we have derived is wrong, of course, we have some mistakes. Well here, it could be that chairman is also the speaker. And in this case, we would have two to the n minus one choices, not n minus two choices to form the rest of the committee. So now we have to make a case distinction, is the chairman the same as the speaker or not? And then our formula gets less nice. So maybe we should dump the whole problem and start with a nicer problem. So let's take a nicer problem this sum, let's actually compare, in this sum you have k squared, and in this sum we have k choose 2. So there is again a nice interpretation, we have a parliament or committee and now, we just select two speakers. So of course, the committee again has n choose k possibilities, and then we just select two members from the committee to act as speakers. So this is k choose 2. And we can again invert this election process. We can say this is our parliament, we first select the speakers. For this, we have n choose 2 possibilities. And then these are really two people. So now, we have to select plus n minus 2 others for the committee. For the n minus 2 others, we have to make a choice whether to include them into committee or not, so we get the following formula, n choose 2, times 2 to the n minus 2. All right, so for the binomial coefficient, it was much easier to derive a formula because we don't have the stupid case distinction, because we said from the beginning that the two speakers must be two different people. All right, so actually we can generalize this and instead of, let's go back here, instead of this. My God here, I made a typo, let me correct this. This should be, this should be k and this should be a. All right, anyway, sorry about that. So the way we do that, again, we have a parliament, a committee. And now we select a, speakers. Speakers. Yes, and this should be k choose a. Just by the same token, we can invert it. First, we select our set of speakers, which is n choose a. And then we select our committee of any size for which we have 2 to the n minus a possibilities. Okay, so we saw a bunch of combinatorial identities and had an intuitive proof using some of these combinatorial interpretations. So, let me actually show you another example because this, we will need later. So, we have this sum here which I can compactly write as this. And actually, we can also starts the summation at zero, it doesn't really make a difference, it's just adding a bunch of zeros, it doesn’t make a difference. And. Okay, how can we derive a formula for this? Well, this is a little bit tricky but here is how you do that. You can take your parliaments, but now, you say it has size n plus 1. And you order your members of parliament from youngest to oldest. Okay. So now, what is our combinatorial interpretation of the sum we have up there? Well, interpretation is as follows, we again select the committee. But now we say the chairman of the committee or the speaker of the committee must simply be the oldest member of the committee. So what we can do is we select the speaker. And then, we select the rest of the committee. So here now, we form a committee of size k plus 1. Okay, we have n plus 1 members of parliament and we want to form a committee of sine k plus 1. The way we do it, we select a speaker, s, and then we select the k remaining members. There is k more members. But from which set? Well, they must be younger than the speaker. We got the speaker, our rule of the speaker is the oldest member of the community. In here, we have s minus 1 choose k choices. So in total, this would give us, we sum overall possibilities for the speaker, which is the sum from s plus 1, and all by a change some variable. This is simply summing up, m from zero to m choose k. So this is it. This is our combinatorial interpretation of the sum. So now, how can we get a compact form. Well, just you know, by selecting the committee in a different way, in a different order. So here is another way. First, we select the k plus 1 members of the committee. So here, we have n plus 1, choose k plus 1 choices. And second, we let the oldest committee member. We'll let the oldest committee member be the chair. So, how many choices do we have for this? Well, simply one, therefore we see, this sum, sums up nicely to this. Right, that's a, and write it up nicely. All right, and now please remember that we have the following formula for the binomial coefficient, m to the falling k, divided by k factorial. Where, we define m to the falling k to be m times m minus 1, and you continue like that until you get k factor. So m minus k plus 1, this is m to the falling k. So, if you substitute this for m choose k, you get the following formula. You get m to the falling k, if you sum up from m equal 0 to n. You get n plus 1 to the falling k plus 1, divided by k plus 1. So, if you have trouble. If you have trouble memorizing the formula. Here is kind of a little melody that might make it easier. So if you for example, take x to the k, and you integrate from zero to y, what do you get? Well, you get y to the k plus 1, divided by k plus 1. Right, so the formula up here is like a discrete analog of integration. All right, so we have just derived this formula. Now, let's see a simple application. You remember two sessions ago, I told you I was frustrated as a high school student because I couldn't come up with a nice formula for the sum of k squared. So now we can, because now we can simply observe that k squared, we can write it as this. That's actually kind of a stupid way to write it. Why should you write it? Well, because this now, 2 the falling k, and k to the falling 2 pluys k to the falling 1. So we can see, we can actually pull out the sum into two sums. And now, from what we have learned, this is k plus 1 to the falling 3. Divided by 3 and here, this is k plus 1 to the following 2 divided by 2. So now of course, we can put that together and you get a nice formula for it. So this is how you can actually derive a nice formula for the sum of k squared and actually for k to the four, and so on. You can try to kind of get a close form for this by the same method. Okay, that's it for today. Thank you very much. [MUSIC]
