Next we're going to take a look at techniques for dealing with coming up with asymptotic expansions when our quantities are expressed in terms of sums. And we'll see lots and lots of need for applying these techniques. A lot of times, our final result is in the form of a sum. So maybe the terms at the end of the sum are much smaller than the terms at the beginning. So we have to use different techniques for different ranges of the sum. So here's an easy example called bounding the tail. So there's a famous problem where the end result is expressed in terms of this finite sum. N factorial sum as k goes from zero to n, -1 to the k over k factorial. So to deal with that one, what we're going to do is write it as an infinite sum, so the infinite sum k greater than or equal to 0, -1 to the k over k factorial. That's just 1 over e, e to the -1. So that quantity that we're interested in is equal to n factorial over e minus this remainder term. And the remainder term is n factorial sum k bigger than n, -1 to the k over k. K factorial. So, now what we can do is just see that this infinite sum, we can bound it just absolutely. It's the first term's less than 1 over N + 1, the next one's less than 1 over N + 1 squared, and like that, which is just 1 over N. So that's a proof that that infinite sum is just 1 over N. And that's just the proof that our original problem is N factorial over E to within O of 1 over N. And again, N factorial grows so fast, that's an extremely accurate estimate of that sub. So that happens a lot, that tail is very small, and we can bound a whole tail at once. Another possibility is that actually the terms in the sum are rapidly increasing. In that case, it might be that the only term that matters is the last one. For example, sum of k, k factorial. So if you just look at the last two terms of that sum, those are n factorial + N- 1 factorial. All the rest of them are all less than 1 over N times N- 1 is N- 1 of them. So, that gets it to within a big O of 1 over N. So you have to have a feeling for how the sum grows, where the big terms are, and where the small terms are. But often, the sums that arise, the terms change in a way that we can take. That we can find most significant part of the answer and express that and then bound the rest of it together as asymptotic expansion. The other thing that we do quite often is approximate with an intergral. And as I mentioned, that's where our approximations for the harmonic numbers and the factorials of the Stirling numbers come from. And we talked about how those approximations and there's proofs of these simple things. But we'll talk about better approximations later on. So, now, those are three basic terms that we use for approximating finite sums, but the main one is approximating with an interval. The classic formula for approximating sums with integrals is known as Euler-Maclaurin summation. And there's two versions of that theorem given in the book and a bit of discussion about where it comes from. Most people are just going to be in the position of wanting to apply the theorem. So I have a finite sum, say k goes form 1 to N of f(k). This theorem gives an asymptotic series for that sum, kind of like a Taylor expansion that is expressed in terms of the derivative of the function. And there's a couple of unique things about this series when it comes to applying it. So one thing is the error correction terms, what are they like? The first one is half f(n), so that's at the end of the integral, it's a little bit left out, say. And then there's a constant that's dependent on the function. Sometimes we have explicit expression for this constant, sometimes we don't. And actually the two cases we gave for harmonic numbers we just name that thing gamma. We don't know how to express it in terms of other mathematical constants. For factorials, for Stirling approximation of log of n factorial, it turns out that that constant is the square root of 2 pi, but that's something that has to be derived independently. And then the next error of terms, the first one is proportional to the first derivative of the function, with the coefficient 1/12. And then usually we stop there because the next one is proportional to the third derivative where a constant of 1 over 720, so it's way smaller. Actually this series, like some other asymptotic series, doesn't necessarily converge. The terms could start to get bigger, so we don't want to take too many. But we can know that since it's an asymptotic series, if we stop with the big O, we can get an accurate result by stopping with just a few terms. And usually, for Euler-Maclaurin summation, we have the integral and just a few more terms. So there's a lot of details about that in the book. But in terms of applying it, just using this form, is very useful for a lot of applications. So classic example f(k) = 1/k integral of f(xdx) from 1 to n is log n. And then [COUGH] the f(n) is 1 over n so that's 1 over 2n. The constant is gamma, the derivative is 1 over N squared so that's that. And then the next term, third derivative's 1 over N 4th. So that gives us the harmonic numbers from Euler-Maclaurin summation to within N to the one-fourth. So for N equals 1 million, you're not going to see deviation from that for 24 decimal places. And the other classic example is Stirling's approximation. And again, now [COUGH] log of n factorial. That's the sum of k, so f(k) is just k, and so, no, sorry, f(k) is log(k), so it's the intergral and compute it out. And again, there's a big jump in precision right at the end, where the last terms big O of 1 over N cubed. So that's going to be a very good approximation for N in the ranges of interest. And we can use that for other functions as well. But these are the classics that arise again and again in the analysis of algorithms. And they're so useful because they're so accurate. So here's a very fine example of applying of the information that we've talked about so far in this lecture. So, if we have Stirling's approximation, just take it to O(1/N). Now what we want to do is use that to figure out how 2N choose N grows, so we want to get 2N choose N to within O of 1 over N. So that's a straightforward exercise using the basic techniques that we've talked about with the algebraic manipulations on asymptotic series. Let's look at how it goes. It's worth doing a couple of exercises of this feature, and there are plenty in the book, because the number of terms that appear daunting. But you have the ability to whack them away with the big O. And a lot of them cancel out. So, let's look at this. So 2N choose N, so that's 2N factorial, over N factorial, times N factorial. So, we have complicated terms multiplied together. We're going to use the x log techniques. So that's equal to E to the log of 2n factorial minus 2log n factorial. So change the multiplication and division into sums of logs. Okay, so now those two functions we can apply Stirling's approximation. So the next line is just plugging in on the first line is Stirling's approximation for log of 2n factorial. That's 2N, that log of 2N- 2N + log of square root of 4 pi N + O(1 over N). And the next line is subtracting off twice, again, the formula for Stirling's approximation. -2(Nln(N) -N + log squared of 2 pi N, plus O(1 over N). So that's the quantity. So now, we just have to do algebra. So and you can see a lot of things are going to cancel out. So say, the first term on the first line is 2N, natural log of 2N. The first term on the second line is -2N natural log N. So that first one is log 2N is log N + log 2, all that's going to be left there is 2N log 2. Then also look what happens to the terms involving square root of pi. So log of square root of 4 pi N minus twice the log square root of 2 pi N. If you just multiply that out, there's a log 2 minus 2 square root of log 2. Minus log square root of N. So log 2 minus 2 log square root of 2, that's 0. So all that's left is minus log square root of pi N. So those two terms go to that one simpler term. [COUGH] And the 2N log 2, that's all that's left. 2N cancels with minus 2 times minus N. And so, now that's 2N choose N equals e to the 2N log2 minus natural log of squared 2 pi N. Now both of those terms have logs and it's e to that powers so now we can undo the technique. The first term is 4 to the N and the second term is, since it's minus, 1 over square root of pi N. So that's an asymptotic expansion for 2N choose N, to within 1 over N. And again, that's a big number. But if we needed to compute 2N choose N over 4 to the N, then we get a function like 1 over square root of (pi)n. And that's going to be what we're going to want to estimate the quantity that we're studying as a typical example. So Stirling's approximation leads us to good approximations of binomial coefficients using the technique. So, there we go. 1 over four to the N, 2N choose N is 1 over square root of pi N. Okay, so, here's an application in the real world of this kind of technique. So, the question is for some kind of computational process, the data might be represented as a binary tree and internal nodes. And the question is, how do you represent that binary tree? You can think about different ways to do it, but one thing that you can know is since the number of trees is the catalan numbers, you have to distinguish among all the trees. So you have to have at least log of that many bits in your representation. Otherwise, the number of things that you represent is less than 2 to that power, and it's got to be at least that big. If you use fewer bits, then you can't possibly represent all the trees. Now someone who didn't know asymptotics might respond to the programmer, that's how many bits you need. But how's the programmer going to compute that value for a million? I have a tree with a million nodes, it's not concise. It's not a value that's easy to compute. Although this is a well known function, maybe, but in general, faced with functions like that, that's not what we want. But using the calculation that we just did, you can say that there's an extra factor of N, 2N choose N, it's 4 to the N over square root of pi N cubed. And we take the log of that log base 2 of that. That's 2n- 1.5 log n. That's really close to 2n. So need at least 2n- so for a million, you'd need 2 million- 1.5 natural log base 2 of a million which is about 20. So you need 2 million minus 30 bits at least, and that's an important practical fact to know. Actually, there's a way to represent binary trees with 2N bits. So that's within 30 of the best that you could do. And so, people who are working with a problem of this sort, could stop there. I know I need at least 2 million minus 30, and I can do it with 2 million. I'm going to be happy with that. And this is not the time to go through this in detail. But the method of representing minor tree in N bits is to just do a pre order traversal of the tree and write down 0 every time you hit an internal node and one when you hit an external node. And that's an unique representation of the tree that you can get back. If you look in algorithm's fourth edition, there's a code for doing that representation. So that's a fine example of why asymptotics are useful. Takes the functions that we get from analysis and it gives us a practical way to work with them. So, that's an introduction to asymptotics and finite sums.
