We will now show that symmetry is not the only remarkable property of Pascal's Triangle. Mainly, let's do the following. Let's compute the sum of all the elements in every row of Pascal's Triangle, okay? So, what we see is that the sum in the first row is just 1, there is a single element. In the second row, it is equal to 1 + 1, which is 2. In the third row, it is equal to 1 + 2 + 1, which is nothing else as 4. In the next one, it is 1 + 3 + 3 + 1, which is 8 and so on. So, you probably already see the pattern. So ,these are just powers of 2, and this is what we're going to prove now. So, we're going to prove that the sum of all the elements in the n-th row of the Pascal's triangle is equal to 2 to the n. Otherwise, we're going to prove that n choose 0 + n choose 1 + and so on, n choose 1- 1 and n choose n, is equal to 2 to the n. Okay? So proves, one is slightly boring and is completely formal. So we can show this just by induction of the number of row. So it definitely holds for the first row and even for the several first rows as we've seen already, right. On the other hand, if we would like to prove this step of our induction that is to prove that because the nth row is the sum is equal to 2 to the n. Assuming that was a previous row, the sum is equal to 2 to the n- 1. What we're going to show actually is that the sum in that very row is twice the sum in the previous row. In fact, going to show this just from the point example, we seem to find things. So, consider this row. 1, 4, 6, 4, and 1. So, the sum is the following, okay. Now recall, that this nice sum pattern in Pascal's Triangle. So, 4 is equal to 1 + 3, 6 is equal to 3 + 3, 4 is equal to 3 + 1. Okay, let's now represent 4, 6, and 4 is 1+3, 3+3, and 3+1, okay. Now let's regroup all our terms, now what we get is 1+1, 3+3, 3 + 3 and 1 + 1. So, in fact, and this holds in general. So, in fact, if we regroup all the terms, if we express the sum in the current from, v as the sum in the previous row, then all of the elements from the previous row appear exactly twice. Which gives us actually that the sum in the current row is twice the sum of the previous row, which concludes is the Proof by Induction. Now let's focus on Combinatorial Proof of this equality, so the recall the sum of k is as usual is the number subsets of size k. When k ranges through all the values of 0 to n. We actually compute the number of subsets of all possible sides from 0 to n, right. So the sum of all and choose k, where k ranges from 0 to n is actually just the number of all possible subsets of our n element set. And this is now into to be the n, and actually it follows from the product through. Since you would like to compute the number of ways of selecting a subset of our n elements set. For each element, for each of the n element, there are exactly two possibilities. This requires take it into yourself or you don't take it, okay. So, the resulting number is 2 times 2 times 2 times 2. So, n such terms, which is 2 to the n, okay. So, another nice property is the following. It is now not about row sums, but about alternating row sums. So, instead of just computing the sum, in each row. Let's compute the following alternating sum. So each subsequent term is taken with either it's plus or minus sign, okay. Then for every row except for the first one, what we see is such a sum is equal to zero. So in the second row, I'm sorry, it is 1- 1. In the next one it is 1- 2 + 1, which is 0 area. In the next one it is 1- 3 + 3- 1, which is again 0. So for some rows, it is immediate that it is equal to 0, just because they are symmetric. For example, this row is symmetric. So, it has 1, 3, 3, 1, and one of these elements begins with plus and one begins with minus. So, it's not surprising that everything telescopes, or cancels out. For this row, it is also immediate. It is also symmetric, right. And each element is taken with plus sign and minus sign. For other rows it is not so immediate but still it can be shown and before this, let's state it formally. So for every row in our Pascal's Triangle except for the first one, the alternating sum is equal to 0. The alternating sum can be represented as follows. So instead of computing just the sum of all possible and chose k, we take and chose k with multiplier- 1 to the k. So this is exactly so,- 1 to the k provides this alternating of sum. So, when k is equal to zero,- 1 to the k is equal to 1. When k is equal to 1,- 1 + 1 is equal to 1. So,- 1 to the k, is equal to- 1 when k is odd, and is equal to 1 when k is even. So, that's use exactly alternation, okay. So, as we've discussed already for some rows, it is, it is just immediate. For some other rows, it also can be shown by using this sum pattern of Pascal's Triangle. Maybe, if you just represent this alternating sum of the current row, via the previous row. I mean, if you replace each element with the sum of two neighboring elements from the previous row, you will see that each element from the previous row is taken once with positive sign and once with negative sign. So everything cancels out, okay. So this is just like a hand-wavey proof, a hand-wavey formal proof, but let's instead begin focus on Combinatorial Proof. So, we need to show that the alternating sum is equal to zero. If we take all the elements with to the [INAUDIBLE] to [INAUDIBLE] what we need to show is that n choose1 + n choose 3 + n choose and so on for all k is equal to n choose 0, n choose 2 and so on, okay. So what basically it states on the left is the number of subsets of even size, and what stays on the right is a number of subsets of odd size. So this is also another nice property. What we're going to prove now, the combinatorial meaning of the equalities that we are proving is the that for every n greater than 0, an n element set has the same number of odd sized subsets as the number of even sized subsets. So to prove this, once again, we're going to establish a one to one correspondence between all such subsets and no such subsets, okay. And for this, we are going to do the following. Let's fix any element x, okay? And we can do this fixing just because n > 0, so at least we have one element. Now we're going to establish this one to one correspondence as follows. One to one correspondence is essentially a partitioning of all the subsets into pairs. We are going to form the pairs as follows. Let's say that the subsets A and B form a pair if they differ just by the element x. Namely, if one gets A by adding the element x to B. So what is written here is that A is B + x, it is slightly informally so more formally in terms of sets A is equal to B union with a single element x. So this x in braces means that we're considering x as a set consisting of a single element x. And here we take union of B and x. So for each, once again, so B is a subset without x and A differs from B just by adding x. It's clear that this is indeed a one to one correspondence, right. We take all the subsets without x and by adding x to them, we get exactly the same number of subsets, right. On the other hand, it is clear that exactly one in this pair of A and B has even size and exactly one of them has odd size, right. Because their size differ by one. So which means that we actually splitted all our subsets into pairs and in each pair there is one subset of odd size, and there is one subset of even size. And this in term means that there are the same number of odd size subsets as the number of even size subsets. Finally here we showing example, if we have, if I would round set and you know if I divided by S has four elements, then on the left will list all its subsets of even sizes, on right we list all its subsets of odd sizes. So now then particulars that we also come. The empty cell, as usual. So the total number of subsets is 16, and as you see the number of subsets of even size is 8, and the number of subsets of odd size is also 8.