We conclude the current lesson with the well-known binomial theorem. So it states that the coefficients of all the monomials in the expression a + b to the power of n are actually the numbers from the nth's row of Pascal's triangle, so let's check this for small values of n, okay? So if one computes (a + b) squared, then this is a well known formula. It give a squared + 2ab + b squared. So essentially, the coefficients of the monomials here are 1, 2, and 1. And these are exactly the coefficients from this row. And another example, if we consider (a + b) cubed, then it is 1 times a cubed + 3 times a squared b + 3 times ab squared + 1 times b cubed. So, these coefficients, 1, 3, 3 and 1 are exactly the coefficients from the Pascal's triangle, okay? Let me also omit just the example for (a + b) to the 4 but as you see these are 1, 4, 6, 4, 1, are exactly the coefficients for the next power of a + b. So more generally, a + b to the n is equal to n choose 0 times a to the n + n choose 1 times a to the n- 1 times b + and so on. So the general term in this expression is n choose k times a to the power of n- k times b to the k and so on. So in the last term is n choose n times b to the n. So in turns of sum, it can be written as follows, a+b is equal to sum over all k ranging from 0 to n of n choose k times a to the n-k times b to the k, okay? For this reason, the n choose k is also called a binomial or binomial coefficient. Okay, so on one hand, n choose k is a number of ways of selecting subset of size k out of a set of size n. On the other hand, it is also a coefficient of the monomial a to the n- k times b to the k. If you open the expression a + b to the n, if you represent it just as a sum of monomials, okay? So as a proof of this theorem is actually straightforward. (a+b) to the n is just the product of (a+b), (a+b) and so on, (a+b) n times. So if you start opening this expression, then of course, from every term you need to select either a or b, right? And in particular, every monomial that you get has degree n. So, you take for example, k b's and then you're forced to take also n minus k a's. And this gives you monomial a to the m- k times b to the k, right? So the degree of this polynomial is n, okay? So, however, there are many, many ways of selecting k b's and n- k a's, right? And the number of ways of selecting k b's is exactly n choose k, right? So you have n terms and out of these n terms, you are going to select k terms from which you're going to select b. So the number of these ways is n choose k, right? Exactly. Okay, so this also can be proved by induction using the Pascal's triangle. So, by induction on n. So for n equal to 0, or 1, or 2, or 3, or even 4, we've already checked this, right? Now let me show you how the statement for n equal to 4, follows from the statement for n equal to 3, and this actually shows a general pattern. So in fact, it uses the sum pattern of Pascal's triangle. Okay, so (a + b) to the 4 is of course equal to (a + b) cubed times (a + b). On the other hand, we already know the expression for (a + b) cubed and I assume that we're proving this by induction. Then all the coefficients just go from the third row of the Pascal's triangle. Now we need to multiply this expression with (a + b) so let's just do this in a straightforward fashion. So a cubed + 3a squared b + 3a b squared + b cubed, when we multiply it by a we get the following expression, okay? Then when we multiply it by b we get the following expression. And they are aligned, now these two expressions are aligned, solve that. We have these three terms here in the same columns. So as you see when you compute the sum of them, this is essentially the same as computing, so this 4 comes as the sum of 3 and 1. This 6 comes as a sum of 3 and 3. And this 4 comes as the sum of 1 and 3. This is exactly the pattern in our Pascal's triangle. And this is true in general, not only for n equal to 4 and 3 of course. So this way of proving the binomial theorem by induction, okay? Now let me show you also some slightly more complicated example, just to show you that binomial theorem allows us to compute the coefficients of all the monomials, not only for the case when we had just a + b. Where instead we might want to compute the 4th power of not just a+b but something like 2a-b. In this case, what remains to be done is just to consider 2a-b as our new a and b. So we consider 2a-b as the sum of 2a and -b. And then for this, for the sum of these two guys we are applying the binomial theorem. This gives us 2a to the 4th, then 4 times 2a cubed times -b times our second friend and 6 times 2a squared times -b squared and so on. And then you just need to multiply these binomial coefficients with powers of 2 coming from 2a, okay? And this finally gives you the following expression. So, in particular, if you have something like 2a- b, to the 7th, for example, you don't need to actually multiply many, many, many terms. You just need to get the seventh row of Pascal triangle, and this will already give you all the coefficients. All what remains to be done is probably to multiply them with coefficients like 2, if instead of a+b, you have something like 2a+b, okay? Now let's also show several interesting consequences of the binomial theorem. For example, if we set a and b = 1, then what we get on the left, so instead of a plus b to the n, what we get is 1 plus 1 to the n, that is just 2 to the n, okay? And this is what we get here. On the other hand, a to the k and b to the n minus k is always equal to 1, because a and b is equal to 1. So on the right, what we have is the sum of all binomial coefficients. So this gives us another proof of the fact that the sum of all binomial coefficients is equal to 2 to the n, okay? On the other hand, if we set a equal to 1, and b equal to -1, and on the left we have 0, right? Because we have 1 + -1 to the n. On the other hand, on the right what we have is just an alternating sum, okay? So this gives us another proof of the fact that the alternating sum is equal to 0. Let me recall, you also, the combinatorial, this means that for any subset, for any n greater than 0, the number of odd size subsets is the same as the number of even size subsets. And the combinatorial meaning of the previous equation is the number of subsets of known element set is equal to the 2 the n. Okay, finally let me show you one more sequence, the one that we haven't seen before. So if we set a =1 and b =2, then what we get on the left, we have a+b which is 3, so 3 to the n. And on the right, we have binomial coefficients and each binomial coefficient n choose k is multiplied by 2 to the k, okay? We have this nice, nice formula. 3 to the n is equal to n choose 0 + n choose 1 times 2 + n choose 2 times 2 squared + and so on, n choose n times 2 to the n. So this is an interestingly looking example but it nicely you'd also have a combinatorial meaning. So let me give you a combinatorial proof of this equation. So what we have on the left here may be viewed as a number of ways of composing a word of length n out of three symbols, we know them by x, y and z. So 3 to the n is of course the number of such words because for every of n positions we have three possibilities, x, y and z. So now our goal is to express this number of word as this sum. And this is what we're going to do now. So let's compute it as follows. So if n chose 0 is the set is the number of all words of lengths n that consist of only of letter x, okay? So n chose 0 is actually 1. So when there is exactly one such word, so it is just x, x, x, x, n times, right? Okay, so we justified this. Now, what we're going to compute next is a number of words containing exactly n-1 letters x, okay? So how to compute it and why it is equal to n choose 1 times 2? Well, it is equal to this expression because of the following fact. To compose such a work, we first need to select exactly one position where x does not appear. So we can do this in this many ways, n choose 1. And then for this position we need to choose either y or z. So we multiply by 2, okay? So this is once again the number of words of things n that contain exactly n-1 letters x. Okay, let me find and then show you the next one, and the pattern will emerge. So, this says as you might guessed already exactly the number of words of length n that can contain exactly n-2 letters x, y, z. Well, again, because to form such word we first need to select two places where there is no x. And for each of these two places, we need to select either y or z. So first of all, there are n choose 2 choices of these two places, and then for each of these two choices, we need to select either y or z. So it is 2 times 2, okay? And this gives us n choose 2 times 2 squared. And in general, if we would like to compute the sum of the number of words that contain exactly n- k letters x, then we first select k positions where x does not appear. And then for each of these k positions, we select either y or z which gives us n choose k times 2 to the k