[MUSIC] [SOUND] Hello, everybody. Last session, we started with a topic of enumerative combinatorics and I showed you how to count basic mathematical objects like functions and subsets. Today, in the next couple of sessions, we'll continue with more sophisticated ways of counting things. As an example, let's play with blocks. So let's take blocks and build a pyramid like this. Okay, it's not a very sophisticated pyramid anyway. So the question I'm asking now, how many blocks do we need to get to a certain height for example six? I mean of course, we can just add up one, three, five, seven, nine, eleven and calculate it but of course, I mean, our goal is to derive a formula that let us do that in a compact fashion. And here is a very nice geometric way to derive a compact formula for this. Let me take this pyramid and let me split off the left half. It's actually a little bit less than the half, but whatever. So, we split off the left part of the pyramid and now we rotate this. And now you see it fits in perfectly and it gives us a square of side length 6. So, of course, we see the number of blocks here is 36. So, you can do that for any height and this actually is a kind of geometric proof that the first n of numbers sum up to n squared. All right, now let's actually not play with blocks, let's play with bricks. So if we build a pyramid with bricks of course, what we are doing, we're going to shift the next layer. So that the two layers are not aligned, but they are shifted. This is kind of a more efficient way to build a pyramid. If mount, we want go all the way up to height 6, how many bricks do we need here? In other words, what is the sum one, two, three, four, five, six? And, again here, here is a geometric shape how to compute that, how to get a formula for this. It's a little bit more sophisticated, so what I have to do I have to actually double the pyramid. So now I have these two pyramids, and I rotate the yellow one. I rotate it and now it fits, and it builds this. It's not a rectangle, it's a parallelogram. Anyway, now we see that every row has seven bricks. Yes, seven bricks, and there are six of them. So, it should be 42, right? So, one pyramid would be 21. And this, of course, can be generalized to every natural number n. The theorem is the first and natural numbers sum up to n plus n(n + 1) / 2. And there is a famous legend about the German mathematician Carl Friedrich Gauss. I mean he was a brilliant mathematician and already when he was in high school, he was kind of brilliant. So there is anecdote that high school teacher gave the class the exercise to just add up the first hundred metro numbers. Something like this, now of course this is not a very difficult exercise but, it's a very boring and time consuming exercise. And maybe the teacher wasn't really well prepared and just wanted to kill time, so but Gauss, as a mathematician, he didn't want to do all the work if there was a smarter way to do it. So what Gauss did, he observed if he takes the sum again but reverses the order in which he adds it up. So he goes from 100 down to 1. And now he adds up term by term, but every term adds up to 101. And how many terms do we have? Well, we have 100 terms, right? So this should be 100 times 101, which is at 10,100. And so the total sum should be half of that. So Gauss was finished, after let's say, three minutes. And whereas the teacher would have expected his students to take an hour or something. So the teacher was actually quite surprised. Cool, okay. So these are the two things we have learned. So when I maybe was in junior high school, I mean, I'm not as brilliant as Gauss. And so I got frustrated that I couldn't find a compact formula for this sum here, so instead of adding up the numbers, you add up the square numbers. And I tried a little bit, but I couldn't seem to get anything meaningful. And of course later I learned that there is a nice compact formula, but it's not as nice. And maybe, so here's kind of a geometric interpretation of this sum. Again but we play with blocks and we take this big square. We put in kind of the smaller square and so on. So we get the three dimensional pyramid and now we're asking how many little cubes are in this big pyramid? And I don't know about you, but I don't see any nice geometric way how to break this pyramid apart and arrange it in a way that gives us a nice formula. I don't know, I don't see any geometric way. And how about this? So we add up the first n binomial coefficients, in just two. Geometrically, this corresponds to something like this, building something like a tetrahedron out of little ones. So, we could take these four guys and build this tetrahedron. And now we're asking, how many little dots are in this tetrahedron? And also here, I don't see a way to manipulate things geometrically to fit into a nice object. So, the geometric interpretation helped us in the beginning. But now, it maybe doesn't help us. And if you think about, more complicated sums like this, or like this, of course we don't have any geometric intuition anymore because this would be like four or five dimensional space. So you see, this playing around with blocks was nice to way to illustrate the proof but it doesn't carry us very far. So if we want to determine a nice formula for these kind of sums, what you need to do, we need to understand a lot about the binomial coefficient. And this will actually be the topic of the next lecture or the next two lectures, trying to understand the binomial coefficient in order to evaluate these sums and count more complicated things. That's it for today, thank you. [MUSIC]