0:20

Hello everybody, at the end of last time,

Â we saw that we need a deeper understanding of the bionoiminal coefficient.

Â N choose k, if we want to obtain compact nice formulas for

Â certain sums and count more sophisticated objects.

Â So this time, we start the battle against the binomial coefficient,

Â let's try to see, let's see how far we get.

Â So the first thing, I want to show you by the binomial coefficient,

Â it satisfies this nice recurrence.

Â So this fact actually have two proves, one is just by pure calculation and

Â one is more about thinking about what n choose k means.

Â So let me give you the proof by calculation first.

Â So remember, we have a formula for the binomial coefficient,

Â which is n factorial divided by k factorial times n minus k factorial.

Â And now we can just plug in the formula into

Â our recurrent appearance to see whether it works out.

Â So let's try to do that, so

Â what is n-1 choose k + n-1 choose k-1.

Â Okay, let's just plug in the formula that we have.

Â This is n-1 factorial divided

Â by k factorial, and here,

Â we get n-1-k factorial.

Â And here we get n-1 factorial, and

Â here, we get k-1 factorial and n-k factorial.

Â 2:09

Okay, let's put the fraction together, so what is the common denominator,

Â the common denominator is k factorial n-k factorial which is already quite good.

Â And the first term, we have to multiply by, so

Â this we have to multiply it by the term that's basically missing down here.

Â Yeah, which term is missing down here,

Â that is n-k, and here,in the right term,

Â the factor that is missing down here is factor of k.

Â So this is times k, and

Â now you see we can factor out the n-1 and

Â get n-k+k divided by this

Â 3:14

So we're done because this is again the formula for n choose k, but

Â this just a proof of your calculation.

Â It's not very inspiring, let me show you a little bit more inspiring proof

Â that actually tells you why this recurrent formula is true.

Â So let this be our set of size n and

Â let's take an element x in the set.

Â Now if you want, if we select the subset of size k, this is a subset x of size k.

Â There are two possibilities.

Â First, we include this element x in our set,

Â and we select k-1 additional

Â elements from the rest.

Â And for this, how many chances do we have?

Â Well n-1 choose k-1, right?

Â Because there's n-1 elements left, and

Â we have to take k-1 from them, or we could choose to not include x.

Â 4:33

We have to select k elements from the rest.

Â I mean from the set without x, so for

Â this now we have n-1 elements left, and we have to select k of them.

Â So the total number of choices is just this plus this, all right?

Â So together,

Â it gives the full number of choices which we have seen as n choose k, right?

Â This is a more intuitive proof of the recurrent formula.

Â All right, so here is a nice thing kind of a fun thing you can do with a formula.

Â So let me write, for example, 3 to 0, 3 to 1 and so on, in one row.

Â What it basically tells you, for

Â choose 2 is simply the sum of these guys upstairs.

Â And 4 to the 4, I mean, technically would be the sum of this, but

Â what do we have here?

Â Well here technically, we have 3 choose 4, but

Â this is of course 0, because you cannot select 4 elements, right?

Â There are not enough elements around.

Â So we can, okay, kind of this, and

Â I mean if you do that so let's fill in the numbers.

Â You see, kind of the first row, we have here is 1 3 3 1, and

Â then the next would be like this.

Â And of course, I mean this row also comes from something.

Â So actually, we can start like this.

Â This would be 0 choose 0, and then this would be 1 choose 0, and so on.

Â And we get the next row by just adding up the two neighbors upstairs.

Â And it goes on like this like 15 20 15 6 1, and let's do one more.

Â Okay, my computer is bugging me about some whatever,

Â some Wi-Fi or something, no idea what.

Â All right, so we get a kind of triangle,

Â where the nth row at the kth position has a binomial coefficient n choose k.

Â And this has a name, it's called Pascal's triangle.

Â 6:57

And a fun thing happens, if you take Pascal's triangle module two.

Â So you're only looking at which numbers are odd and which are even.

Â So let's mark all the odd numbers, so these are odd, this is odd,

Â and then this is odd, and here this is odd, this is odd, this odd.

Â So we get kind of a certain structure, and if use a computer to plot this,

Â or you simply to go Wikipedia and look at the figure, you get this kind of

Â nice fractal like object which is called Sierpinski triangle.

Â 7:51

Another important thing with a binomial coefficient appears as

Â the following formula.

Â So in high school, you might have learned

Â the following formula x + y squared is x

Â squared + 2xy + y squared.

Â And maybe you even remember the formula for this.

Â Anyway, but today we will see a formula for general n, which is the following.

Â It's called the binomial theorem x + y to the n is this complicated sum, and

Â let me explain it a little bit.

Â So here, this is an expression with two variables.

Â This is called a binomial and this is it's coefficient, right?

Â In this expression, and therefore it's named binomial coefficient there is

Â where the name actually comes from.

Â So again, I want to show you to proof of the theorem.

Â First one with a lot of calculation, and then approve with just thinking.

Â Here's the first proof.

Â 9:11

Our base case is that n = 0 in which case x + y to the 0 is 1.

Â And the right hand side would be the sum from 0 to 0,

Â 0 choose k, x to the ky to the 0-k.

Â You can easily check this, it's also 1.

Â So for the step, we suppose the formula is correct for n, and

Â we have to prove it for n + 1.

Â So what is x + y to the n + 1?

Â Well one thing that is easy to see, it's x + y times x + y to the n.

Â So now by induction, we can plug in the formula for x + y to the n,

Â because we can assume by induction that the binomial theorem is true.

Â Here's a little trick to make things a little bit easier.

Â In this sum, we sum up from k = 0 to n, but actually, you can convince yourself,

Â we can actually sum up of all values k, of all integers k.

Â Because if k is not in this range, for example, is k is negative or

Â larger than 0, then n choose k is, if you look into the definition anyway 0.

Â So by just letting k run over all integers, we just add a bunch of zeroes.

Â So we don't change the sum, but it makes the proof a little bit easier.

Â Okay, so we use the induction hypothesis and

Â see that this is x + y times n choose k,

Â x to the k and y to the n-k.

Â And now we can expand this product,

Â we get x times the sum plus y to the sum, so we get now two sums.

Â The first sum, we multiply by x, so we get k + 1 up here,

Â and the second sum we multiply by y.

Â So, x to the k,

Â y to the n+1-k.

Â And now we do some little trick that's called a change of variable.

Â We say, hey, look in this sum,

Â we renamed k + 1 to bj.

Â And if we do that, then we get over here the sum of all j,

Â now you have to think what is k?

Â Well k is j-1, and then now we get x to the jy,

Â and now you have to think what is n-k?

Â Well n-k turns out to be n+1-j, and

Â here, we simply get the same sum.

Â 12:03

And now you see the change of variable,

Â because we set to k ranges over the whole integers.

Â Now we set j to be k + 1, it also ranges over the whole integers.

Â So we don't need to keep track from where to where the variable runs.

Â And this makes the change of variable a little bit easier,

Â we just have to think less.

Â And now you see, this term here, it's the same as here.

Â So now we can pull the two sums together,

Â and we actually get the sum over all k, x to the k,

Â y to the n+1-k times the sum of these two things times.

Â Let's see whether I have enough space,

Â n choose j-1 + k-1, now change the name back n choose k.

Â And by our recurrence formula, we know that this is simply n + 1 choose k.

Â 13:51

If you think about it,

Â this is a sum of 2 to the n terms, right?

Â If you multiply it out for every combination you get a sum of, so

Â you get 2 to the n total.

Â And when do we get like x

Â to the k time y to n-k?

Â Well when we select, x

Â in k out of on all n (x + y),

Â and there are n choose k ways to select that.

Â And therefore, the coefficient of x to the k times y to the n-k is exactly

Â the binomial coefficient n choose k.

Â