[MUSIC] Binomial coefficients can be arranged in a triangular table which is called the Pascal triangle. So let us arrange the binomial coefficients in the form of the following table. So it's rules are indexed by integers from zero up to infinity, 0, 1, 2, 3, 4, etc. And in each row, we write down all the binomial coefficients. n choose, let's say n choose 0, n choose 1, n choose 2, etc. So here is 0 choose 0, 1 choose 0, 1 choose 1, and so on. So in the fifth row, we have 5 choose 0, which is 1. 5 choose 1 is 5, as we have discussed. 5 choose 2 is 10. 5 choose 3 is the same as 5 choose 2, it is again 10. 5 choose 4 is 5, and 5 choose 5 is 1. And let's also write down the sixth row, 1, 6, 15, 20, 15, 6, 1. The recurrence relation on the binomial coefficients gives us the rule for constructing the Pascal triangle. It says that the sum of two neighbors, namely (n-1) choose (k-1) and (n-1) choose (k) is equal to, n choose k. So if we take two neighboring entries in one row, they add up to the element below them. And the Pascal triangle is a useful tool for dealing with binomial coefficients. When we look at this table, we can observe many interesting properties of the binomial coefficients. For instance, let us take the sum of elements in each row. So in this row, there is only one. In this row, we have 1 plus 1, it is 2. Here we have 1 plus 2 plus 1, it is 4. Here we have 1, 3, 3, 1, making 8. In this row, we have 16, 32, 64, and so on. So here we get the powers of 2. Here is an observation that we made that, let us list it as Property (5). Of the binomial coefficients, it says that n choose 0 plus n choose 1, plus etc, plus n choose n, is 2 to the power n. How to prove this identity? Well, one possible way of proving it is by induction. We need to show that the sum of all entries in each row is twice the sum of entries in the previous row. Indeed, we can use this property, saying that each element in the subsequent row is obtained as the sum of two elements in the previous row. So when we take the sum of all elements in this row, we need to take the sum of all elements in previous row, taking each element twice. This means that the sum over here is twice the sum of elements in the previous row. And we received by induction. This is one possible proof of this identity. But now let us give combinatorial proof. So we know that the binomial coefficients enumerate the k-element subsets of the set of n-elements. n choose k is the number of k-element subsets. So the sum of n choose k, for k from 0 to n, is the number of all subsets of a set {1, etc, n}. And we can list all subsets of this set in a different way. A subset means that for each element, we need to decide whether we take it or not. So the number of subsets is the number of maps. The number of maps from {1, etc, n} to the two element set {0,1}. So if k maps to 0, this means we do not take it into the subset. And if it is mapped to 1, then we take it into the subset. So the number of such maps, as we know, is nothing but 2 to the power n. And so this means that the total, the sum of all binomial coefficients n choose k, for k from 0 to n, sums up to 2 to the power of n. Now let us discuss Newton's binomial theorem. It's where the name binomial coefficients come from. The binomial coefficients are called in this way because they occur in the expansion of, The expression (a + b) to the power n. Namely, this expression is equal to the sum n choose k, a to the power of n minus k, b to the power of k, where k ranges from 0 to n. So this is the same as, a to the power n, plus n a to the power n minus 1 b, plus n(n- 1) over 2, a n minus 2 b squared, plus etc, plus na b to the power n minus 1, plus b to the power n. So when, n is equal to 2 or to 3, you recover the familiar formula for the square or the cube of (a + b). So say a + b squared is, a squared plus twice ab plus b squared. And (a + b) to the power of three is, a cubed plus 3a squared b plus 3ab squared plus b cubed. So in the expansion of (a+b) to the power n, you have exactly the binomial coefficients from the nth row of the Pascal triangle. Let us prove this formula, indeed. Let us compute the left hand side, As the product of and factors of the form (a+b). So let us compute the coefficient in front of a to the power n minus k b to the power k. Compute the coefficient in front of a to the power n minus k b to the power k. This means that if you have n brackets here, from each bracket you can take either a or b. And to get the coefficient of this form, you need to take exactly k b's. And all the remaining entries, n minus k of them, will be a's. So you need to pick k brackets where you get b from. And you get a's from the remaining ones. So you need to point out a k element subset over this n element, set over brackets. And here we have n factors. Okay, so this means that the coefficient in front of a to the power of n minus k b to the power of k, is the number of k element subsets of the set of n elements. It is, It is equal to, The number of k-element subsets of {1, etc, n}. So the brackets where the b's come from. And this is equal to n choose k. So all the factors in the expansion of this expression are equal. I have this form, a to the power n minus k times b to the power k. So we have found, all the coefficients in this expression. So the Newton's binomial theorem is proven. Okay, from the Newton's binomial theorem, you can easily get another proof of Property (5). Namely, what happens if you evaluate this, the left-hand side and the right-hand side, at a equals b equals 1? So another proof of (5). So by Newton's binomial theorem, (1+1) to the power n is equal to the sum of the binomial coefficients n choose k. And all these factors will be equal to 1, 1 to the power n minus k times 1 to the power k. So this means that the sum of binomial coefficients in the nth row of the Pascal triangle is 2 to the power n. And another closely related property is Property (6). What happens if you take an alternating sum of the binomial coefficients in the nth row? What if you take them alternatively with plus and minus signs? So n choose 0 minus n choose 1 plus n choose 2 minus n choose 3, etc, plus (-1) to the power n, and to n choose n. I claim that this is 0. The proof. Another algebraic proof of this property is, take in the binomial theorem, a equal to 1, b equal to -1. Then, or vise versa, it's not important. Then you will get this expression, on one hand. So (1- 1) to the power n will be equal to the sum of (-1) to the power of k times n choose k. And this will be equal to 0, so this is an alternating sum. As an exercise, you can try to invent a combinatorial proof of this identity. This is also not very hard. So in this lecture, we have given the definition of binomial coefficients and discussed some of their properties, such as their recurrence relation, the relation to the Pascal triangle, their appearance in Newton's binomial theorem, and some other properties. And in the next lecture, we'll see how they appear in other combinatorial problems. [MUSIC]