[MUSIC] Hello every body welcome back. In the last few lectures we have seen a lot of things about the binomial co efficient and chose k for example several combinatorial identities we have derived exact formulas for several complicated sums. And we have also seen the big O notation. And one message from lecture from the big O notation was that sometimes, it is better to get a rough estimate of something instead of trying to figure out completely the truth. So, sometimes, kind of rough estimates are enough. And this is what today's lecture is. We try to determine the size of n choose k. So for two numbers n and k, how large is n choose k roughly? So here's the first lemma. N choose k is sandwiched between these two expressions. Let us try to prove that. First the upper bound is pretty easy inches k. One of the formulas we have learned is it's into the falling k divided by k factorial and n to the falling k is of course less than n to the k. Which proves the upper bound All right, so 2nd for the lower bound, we have to peek a little bit more Into what these things means. So, n to the following k is the following expression n- k + 1, in here k (k- 1) and so on. Well, just times 1 here, okay, so you see in numerator and denominator both have k terms. So we can somehow chops them up and group this and this and so on. And now you see which of them is actually the smallest while the first term is the smallest. So we can, we are on the safe side if we say this is n over k to the k. So we are on the safe side. All right, very simple. In fact there is slightly more precise estimate, it's this n over k to the k is lower bound. And for an upper bound, you just take the same but you put in a factor of e here. I don't want to prove that. I mean, we'll use it occasionally but I don't want to prove this bound. We'll prove another bound and use k later. And let's see a quick application through example n through squared of n, what is it? Roughly, so first we have seen, As a lower bound it's n divided by square root to the square root. So this is just square root of n to the square root of n, and as an upper bound on, you see this is at most e times n divided by square root of n. This is e times square root of n to the square root of n. And you can rewrite this as, for example, e to the one half ln square root n. And here this would be e to the 1+one-half n times square root n. So you see in the kind of suggestive way that I wrote it t1he estimate seems to be pretty precise. But how about something like this, can we get a good estimate, can you get a good grasp on how large this should be? So what is our upper bounds? Our upper bound is e times n divided by n over eight raised to the n over 8, and this now is 8 times e to the n over 8. This it turns out, is actually quite bad about. It's really bad, I mean, what is this? This is something like well I don't even want to talk about this estimate is very bad. So once so if you have n to k once k is omega of n so something like n over 8 or even n over 100 or so t1his estimate is very bad, so the estimate e times n over k to the k is a very bad estimate. All right, this is a very bad estimate. Can we get better ones? Yes, we can, but let's do a quick interlude. Let's ask ourselves, of all the binomial coefficients, which is the largest? So which is largest? So let's see, right? I mean, let's compare inches k plus 1 and then inches k. And see whether this is larger than zero or smaller than zero, larger than one, smaller than one, whatever. So we get the following. This is k plus one factorial, n minus k minus one factorial. And for this we get n factorial here, k factorial n minus k factorial. So you see this is n- k, divided by k + one. Okay, so, this is Larger than one, as long as n- k is at least k + 1 so at as long as k is at most n- 1 over 2. And it is, yeah okay so you see basically inches k is this if this is k This basically means, it increases, increases, increases, increases up to here and then, at some point, it decreases again. All right? So, you can also figure out, it is, Well, let me think. Did I make a mistake? Tk, no, that seems fine. Okay, so basically what this proves is the following: among the binomial coefficients, the largest term is n2 over 2 if n is even and if n is odd, then it's the two middle terms you get. So this one and this one. So what does it help us to determine the size? Well, it helps us to determine the size of this binomial coefficient Because first of all, we know it's at most 2 to the n. Why do we know that it's the upper bound? Well, because this here, By the binomial theorem is 1+1 to the n is 2 to the n and this is a sum of n+1 terms. So the largest of them must be at least everything divided by n+1 and that explains the lower bound. We've determined the size of this guy up to a factor of n+1, okay? This is good for n choose n/2, but what does this help us to determine the size of something like, n choose k? Well, Here is how you do that. So we want to determine the size of this and we can of course not argue anymore for general k that n choose k is the largest of these terms. But maybe if we are smart, we can make it the largest. So suppose I take some value x and I multiply it by x to the k and I sum up over everything, by the binomial theorem I get, 1+x to the n. All right, and now maybe we can choose x such that our desired binomial coefficient. So let's say that x to the k n choose k is maximized For k = r, for example. And if we know this, then we have a good approximation for n choose r. So let's see which, let's call this term Tk And let's see which k maximizes Tk. So you can do, we can take Tk+1 / Tk. This is x to the k n, mm-hm, and here we have plus 1. Actually, let me write it properly. X to the k+1 and down here we have, x to the k. So this is x times, and now actually let's go back and simply copy what this is. It's n- k / k+1. n- k / k+1. And you see Tk keeps growing as long as this is at least 1. So Tk is less or equal than Tk+1, as long as, This is at least 1, which is as long as. Well, actually let's leave it at this. I'll not set x = k/n. So x to be k/n and then you see that, That x times n-k / k+1 is, no wait, x = k / n-k. There you go. Okay, x = k / n-k. So this term here, Tk+1 / Tk equals this. Yes. N-k / k+1. So this is k / k+1, and you see this is, Less than 1. On the other hand, Tk / Tk-1 is, and now it's again, x times what? Now we have to be careful. We have to replace k by k minus 1, so we get this divided by k. So this is k / n-k times this Which is lager than 1. Okay, and this is super nice because now you see that Tk-1 is less or equal than Tk and this is less or equal than Tk+1. And you actually see, no wait, Tk is bigger. It's bigger than both its neighbors and if you think about it, this also easily proves that Tk, Is max. So very nice, but what does this help us to determine the size of n choose k? Well, again, if we take the sum here, now let's write j from 0 to n are n choose j. We know which term is the largest, it's the one in the middle. But how does it help us to determine the size of n choose k? Well, here is a very nice trick. What happens if I put in x to the j here? Then by the binomial theorem, this is 1+x to the n. Now maybe I can select x. Such that this term here, let's call it Tj, such that Tj is maximized By j = k So in order to figure this out, we have to compare Tj and Tj+1. So Tj+1 / Tj = x to the j+1, n choose this. Which is x times n-j / j+1 And now, we just set x to be k / n-k. And with this, we see that Tj+1 is larger than Tj. Whenever. Whenever this is larger than 1, larger or equal than 1. And now you see, actually A quick calculation gives you that this is actually the case as long as j is less than k. So, T0 goes up All the way to Tk, and then, it goes down. That means t k is exactly the one that maximizes so it's k is exactly the one maximizes t k so therefore we see the following, This sum is at least the term number k, which is x to the k inches k. But it also at most, n plus one times its largest term, which is also tk. So now you see that n choose k Is at most, what? Is at most the sum, which is 1 plus x to the n divided by x to the k. And is at least the same thing. Or times this vector of n + 1. So if you don't care too much about this vector of n + 1, then, this here already tells you the truth. So now, let's evaluate this term and remember x is thus here. Well, let's again write this down, x is k divided n- k and we know that n shows k is x to the k divided by 1, no the other way around. Let's go back. Yes, 1 plus x up here to the n. Divided by x to the k times something that is between 1 divided by n plus 1 and 1. Okay, so now let's evaluate this term here. This is 1 + k divided by n- k to the n divided by k over n- k to the k. And now this calculation to try to get a good expression here. So this is n divided by n- k. And this is k to the k and the n minus k to the k gets up here. Now what is this? Well, this cancels, so it's n to the n times n- k to the n- k divided by k to the k and we can nicely write it as n over k to the k and n divided by. Wait, there's something wrong. Okay, of course. This is, it's supposed to be k- n. Yes, k minus m that's nicer. So we can write it as this. Right, now what is k? K is roughly proportional to n. So k is r times n and r is something like 1 over 8. And this has a kind of very nice form. This is 1 divided by r to the rn times 1 divided by 1- r, 1- r x n. And now, let's focus on this term. So, this is predictably let me put big parenthesis about it and delete the n here. And just pull it out. You can write it as two to the- r log r- 1- r log r 1- r, right, we're just rewriting r as 2 to the log r and this beast in here is very important. This is called the binary interpre function, this is called H(r). And finally, we have the following compact formula. All right so let's write up nicely what we have learned n to r times n is 2 to the binary entropy of r times n times some number that is somewhere between this and one. And actually what kind of number this is, it can be determined a little bit more precisely. But you see what you have here, if r is some number, if r is 0.2 or something, this is exponential in n. So this is already so vague so we don't really care about the factor 1 over n + 1 or something anymore. So for certain values of r, if r is a constant between 0 and 1, this is the best estimate that you can get from the final main coefficient and yeah. So this formula you should really keep in mind, thanks. [MUSIC]
