Transcription
[SQUEAKING] [RUSTLING] [CLICKING]
BRYNMOR CHAPMAN: Hello. Can people hear me?
[SIDE CONVERSATION] Hello?
[SIDE CONVERSATION] Getting some thumbs up.
[SIDE CONVERSATION] OK. Why don't we get started? Hello, everybody. I'm Brynmor. If you've been coming to lecture, you've already met Erik and Zach. I'm the third instructor for this course. Today, we are going to switch gears a little bit. So we're going to move on from state machines. And we're going to start a new unit on algorithmic analysis. So we'll be looking at that until the end of next week. This lecture is going to be about sums. OK.
So sums are quite useful. As I hinted at a moment ago, they're good for algorithmic analysis. You'll use everything in this unit quite a bit if you take 6.1210 or any other algorithms course. They're also useful for things like probability, counting, machine learning-- everything's useful for machine learning nowadays-- recurrences and a bunch of other things.
So let's start with an example. OK. Has anybody here ever won the lottery? Hands. Nobody? Really? Oh. Come on, guys. OK. Well, does anybody know how it works? So if you win $1 million in the lottery, it turns out you don't actually get a check for $1 million in the MAIL. Or you do, but it won't cash. It actually comes in installments. OK. So imagine you get $50,000 now and $50,000 next year and so on for the next 20 years. So in total, it ends up being $1 million in some sense. Right? But does it have the same value? Who would prefer to have $1 million right now? Lots of hands. Who would prefer to have the installments, $50,000 per year for 20 years? Well, a few hands. Can I get some reasons?
AUDIENCE: So you don't waste it all at once.
BRYNMOR CHAPMAN: Oh, that's an excellent reason. Supposed to be. Anybody else? A reason either way. Yeah?
AUDIENCE: Inflation would make [INAUDIBLE].
BRYNMOR CHAPMAN: Sorry?
AUDIENCE: Inflation will make the installments less valuable.
BRYNMOR CHAPMAN: Yeah. OK. So that's an argument for getting the million dollars right now. Right? The $50,000 you get in 20 years, if a gallon of milk costs $4 today and $10 in 20 years, that $50,000 isn't going to go so far. So at least in terms of the actual buying power of the money, you'd really prefer to have that $1 million right now because money now is more valuable than money in the future, inflation or, relatedly, you can invest this money and it'll end up being more worth more in 20 years. So this is exactly how a loan works, right? You get a lump sump of money now. And you pay it back in installments. And you account for interest. So this is what's known as an annuity.
So for an annuity, we're going to make some fairly simplified assumptions. We're going to assume a fixed interest rate. Let's call it p. So as an example, the Federal Reserve says that interest rate right now is about 5.33% So let's just take that as a working example, or at least that's what it was at the beginning of the week. I haven't checked it today. And we're going to get m dollars every year for n years. So in the example that we were just looking at, m is 50k, n is 20 years, and we've got this interest rate p, 5.33%. OK.
So what does this mean about the value of money over time? Well $1 now, if we get this $1 now, it's going to be worth or it's equivalent to getting 1 plus p dollars one year from now. Does that make sense to everybody? If I take my $1 now and I invest it, I'll end up with $1.05 in a year. OK. Or in two years, it'll be 1 plus p squared or, in k years, it'll be 1 plus p to the k. Conversely, what if I get that dollar in 10 years? How much is that worth in today's money? Anybody? Hand. No? Are we still asleep? Too early in the morning? OK. Well, conversely, if I get my dollar in 10 years, it's going to be worth 1 divided by 1 plus p to the 10th. Does that make sense to everybody? Yes, no, kind of, thumbs up? A few thumbs up. OK. Good. I'll take it. OK.
So basically, what's going on is we're getting m dollars now, m dollars in one year, m dollars in two years, OK, dot, dot, dot, up to n years. And we'd like to figure out what the equivalent value is today. So this m dollars now, now this is worth m dollars today. OK. This m dollars in one year is going to be worth-- whoops-- m times 1 plus p to the minus 1. OK. This m dollars in two years is going to be m times 1 plus p to the minus 2, et cetera. And the m dollars that we get in n years is going to be m times 1 plus p to the minus n. I guess this is n minus 1, right? Yeah. We're starting at 0 years. Does that make sense to everybody? So what is the total value? The total equivalent value in today's money? OK. We'd like this in a closed form. So right now we've kind of got-- we're trying to sum all of this up. Right. But it's not a very nice expression. OK. We'd like a closed form, something that you can put into one of those old-fashioned calculators if you've ever seen it, those things that you hold in your hand and push the buttons on it? No. Oh, yeah. There are some old souls in the audience. OK. But yeah. We don't want any ellipses like this or sigma notation or anything like that. We just want a nice, clean expression that you can put into a calculator. So how can we go about computing it? Any ideas? What if we were to replace this 1 plus p with an x? Would that make it any easier? So we've got m plus mx plus mx squared plus mx to the n minus 1. Are people happier with this expression? Getting some nods. OK. What is it? Anybody remember? Yeah?
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: Yeah. It's a geometric series. OK. So this is going to be m times 1 minus x. Oops. n over 1 minus x. So we knew this expression already. How could we check it? Or how did you check it? I believe you already have. Yeah?
AUDIENCE: Are you sure that's the [iNAUDIBLE]?
BRYNMOR CHAPMAN: Oh. Thank you. Yeah. Yep. You're right. Thank you. So how could you prove this? Or how would I have failed to prove it if I tried to do it just now? Yeah?
AUDIENCE: Subtract it?
BRYNMOR CHAPMAN: Yeah. OK? So this is what we call the guess and check method. So if we've got a sum like this, and we know or we can reasonably guess a nice closed form for it, then we can prove it by induction. That's fairly straightforward. The hard part is figuring out what that closed form should be. And in this case, the inductive step reduces to some fairly simple algebra as you already saw, I think in recitation. Is that right? Rec 02 maybe? Yeah. Yes. Thumbs up from Zach. Even if you don't remember, Zach does. [LAUGHS]
So how might we discover this closed form if we didn't already know it, though? Any ideas? Yeah?
AUDIENCE: Multiply the series by [INAUDIBLE].
BRYNMOR CHAPMAN: Yeah, exactly. So this is what we call the perturbation method. So the answer was if we multiply this entire thing by x and subtract it, then things will cancel. So this is one example of what we call the perturbation method. This is something that-- does anybody know the story of Gauss in the kindergarten or first grade when he was given a massive sum to evaluate by his teacher and 3 seconds, he gave the teacher his answer and the teacher is like, what the hell? No, go back to your seat. OK. Yeah. So perturbation method in action. So Gauss was asked to evaluate 1 plus 2 plus-- I think the story was 100. Not actually sure. And Gauss observed that if you take this series and perturb it a little bit, so in this case flip it around, and then add them together, you end up with something very nice. Right? So he's got two copies of this sum. So two S is equal to this thing, which means that S should be equal to that. So fairly straightforward. We can do the same thing with this geometric series here. So for simplicity, I'm going to drop the m. So if instead we have s equals 1 plus x plus x squared plus x to the n minus 1, and here your colleague said that we should multiply this by x. So Sx equals-- I'm going to shift everything over so that it's a little bit easier to see what's going on. And now this time instead of adding them, we're going to want to subtract. This 1 doesn't have anything to subtract. And now here we've got plus x minus x plus x squared minus x squared. So everything is going to cancel until we get to the end. And here we've got minus x to the n. So now we've got S minus xS is equal to 1 minus x to the n which means that S is 1 minus x to the n over 1 minus x. So if we didn't know the formula for a geometric series off the top of our heads, which I clearly didn't, we could derive it like this and then we can check it by induction. Does that make sense to everybody?
So if we go back to our annuity example, we had-- so m was 50k. n is 20 years. p was 0.0533 which means that our x here was-- was it 1 over 1 minus p? 1 over 1 plus p. So if we plug this in, it turns out that the value of our annuity is actually about 638,000. So it's not just less than the $1 million that we were promised. It's like substantially less. Right? What if we took an even more extreme example? Like suppose instead of $50,000 per year for 20 years, we got $1 per year for million years. For simplicity, let's just say it's forever. So suppose we get $1 forever, like every year forever. How much is that worth? Half a million, 100,000? Yeah?
AUDIENCE: $20.
BRYNMOR CHAPMAN: Yeah. About $20. So this x to the n just goes to 0. Turns out that if we have m equals 1, n is infinity. Same p as we had before. It's about 20. So it might be a little bit counterintuitive that getting money, like, forever, it still has finite value, right? But yeah, I don't know, maybe if you think about it, it kind of makes sense. Like that money that you're getting like n years from now, who cares? You're not even going to be alive to use it, right? So maybe it also kind of makes sense that it's not worth very much. And in the real world, there are actually perpetual annuities like this. They do exist. I believe there is a surviving one issued by a Dutch water company in the 17th century. I think they issued five that are still around today. And one was acquired by Yale in, let's see, maybe 30 odd years ago, I think, for $24,000. And it gets them about $12 annually so only worth it for the historical value. The money is a complete wash.
So are people reasonably happy with the perturbation method? Yeah? Some thumbs up? OK. So Let's move on to a slightly different method for evaluating other sums. So this is what's called the ansatz method. Am I spelling this correctly? I hope so. Or if you don't like German, I think it is, you could also just call it the educated guess method. So suppose we have the following sum. Sum from k equals 1 to n of k squared. OK. So first, does anybody already know the answer? What does the sum evaluate to? Oh. Nobody. OK. In that case, next question is open to everyone. Does anybody have any idea what vaguely the solution might look like? Yeah?
AUDIENCE: It should be some sort of cubic.
BRYNMOR CHAPMAN: Yeah. It should be some sort of cubic. We're summing up a bunch of squares-- well, n squares. A bunch of them are about n squared. And so we should get something that's about n cubed. So guess S is approximately n cubed. Now, it won't do us too much good to put that into our guess and check method. Yeah?
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: Intuition, basically. So one way you could think about it is so half of these terms are going to be larger than n over 2 squared. So that's one fourth of n squared. You've got n over 2 of those. So you should have something that's at least one eighth of n cubed. Does that make sense? And then for an upper bound, you've got n terms which are all at most n squared. And so it's going to be something between one eighth n cubed and n cubed itself. Does that make sense? We're hinting at something else that we'll do a little bit later. If you squint really hard, a sum kind of looks like an integral. So if you integrate that, you're going to get something that looks like n cubed. OK. Another question?
AUDIENCE: Oh, my question was just if you could write down [INAUDIBLE] so that it's easier to visualize, like some of them are greater than n [INAUDIBLE] squared and some of them are less.
BRYNMOR CHAPMAN: Yeah. We could do that if you like. So we've got 1 plus 2 squared plus 3 squared plus n over 2 squared plus all the way up to n squared. So these terms, plus or minus 1 term if it's even or odd, so these are all greater than or equal to n over 2 squared. And we've got n over 2 of them or n over 2 plus 1, or whatever. So the sum is going to be at least n over 2 squared times n over 2 is one eighth n cubed. OK. Yeah? Question.
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: Ah. OK. So we're getting a more refined guess. So actually, I would argue that n cubed is already good enough for what we're doing anyway. And here's why. So as we said, it's not very precise. Right? We don't know, like you said, the leading coefficient should probably be 1/3. But we're just going to start from guessing that it's a cubic of some sort. We don't know anything about the coefficients, but it seems like a reasonable guess. So we're going to say that S is equal to a times n cubed plus bn squared plus cn plus d. We're just going to take that on faith, assume it, and see where it leads us. So if we assume that, what can we deduce? Any ideas? How might we go about figuring out what a, b, c, and d should be? Well, what if we look at, small n? So if we have, say, n equals 0? What happens if we put in n equals 0?
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: Exactly. OK. So then we have a times 0 cubed plus b times 0 squared plus c times 0 plus d equals what? What is the value of our sum at 0?
AUDIENCE: 0.
BRYNMOR CHAPMAN: 0. Yeah. We've just got the empty sum. What else can we do?
AUDIENCE: You plug in n equals 1.
BRYNMOR CHAPMAN: Yeah. n equals 1. That seems like another decent choice. And so this time, we'll end up with a plus b plus c plus d equals what? What's the value of our sum there?
AUDIENCE: 1.
BRYNMOR CHAPMAN: 1. And if we continue like this, we get 8a plus 4b plus 2C plus d equals 5, so 1 plus 4. Question.
AUDIENCE: Do we have the values of a, b, c, and d?
BRYNMOR CHAPMAN: No. We're trying to figure those out. So we're just taking it on faith that S has this form.
AUDIENCE: But if n equals 1 then we solve one.
BRYNMOR CHAPMAN: So we already know that because S was defined as the sum of squares. So if we sum up all of the squares up to n equals 1, we get 1. If we sum them up to n equals 2, we get 5, cetera. Is this enough?
AUDIENCE: Need one more.
BRYNMOR CHAPMAN: Yeah. We need one more. So let's put in n equals 3. Here we've got 27a plus 9b plus 3c plus d equals 14. Can I arithmetic at least? I think I can arithmetic. 1 plus 4 plus 9. That sounds like 14. OK. So now we've got a system of four equations and four variables. So we should be able to solve it. OK. Has anybody figured out what the solution is yet? Well, d equals 0. That's an easy one. I think it turns out to be a equals 1/3, b equals 1/2, c equals 1/6. Is that right? And yeah, d equals 0 because we've got a bunch of zeros here. OK. So are we done? Have we found our solution? Yeah?
AUDIENCE: Got to prove the values.
BRYNMOR CHAPMAN: Yeah. So we've maybe found our solution but we don't know. We just pulled this out of a hat and assumed it. So we should actually prove that this is correct. So now we're going to take S equals 1/3 n cubed plus 1/2 n squared plus 1/6 n and use that as our guess and go back to the guess and check method and prove this by induction. We're actually going to want strong induction. These are our base cases. We've already proven that, essentially. That's what we used to derive a, b, c, and d. And our inductive step is just going to be a bunch of algebra. So I'm not going to go into that right now. But yeah, if you're interested, feel free to prove it. OK. Yeah. And if it works, we'll have a proof that our formula was correct. And if it doesn't, we go back to the drawing board. We know that this form was wrong. And so maybe we try and figure out a different form that our answer might take. Does that make sense? Are people happy with that? Any questions? Maybe I should phrase it the other way.
AUDIENCE: What's your name?
BRYNMOR CHAPMAN: Oh. I'm Brynmor, like the Pennsylvania College. Same word spelled differently. I saw another hand over here. Was that a question or a--
AUDIENCE: Your 1/3, 1/2, 1/6, that's just like if you do the algebra pretty much?
BRYNMOR CHAPMAN: Yeah. So that's if you solve this system of equations. That's what comes out. You could do Gaussian elimination, or invert the matrix, or whatever.
AUDIENCE: But if you didn't know that, did you just know that because it was on your notes or did you have a way to figure it out instantly, like the way you just wrote it?
BRYNMOR CHAPMAN: Oh, no. I'm not that good.
AUDIENCE: All right. I'm just checking.
BRYNMOR CHAPMAN: Oh, I mean, no, I totally don't have it on my notes. Yeah. Yeah. Question.
AUDIENCE: Is there any particular reason you chose this form as your educated guess? [INAUDIBLE]
BRYNMOR CHAPMAN: Yeah. So as we were discussing before we dove into it, we think that it's probably going to look something like n cubed. We don't know exactly how close it is to that, but it's kind of reasonable to assume that it's a polynomial like a cubic polynomial. So maybe we could have started with something like this instead. Like maybe it's some constant times n cubed plus quadratic term. And then the ansatz method would have failed. We would have ended up with suspicious looking guess. We would have tried to prove it by induction and it wouldn't have worked. But yeah, as it turns out, this is a reasonable guess. Yeah?
AUDIENCE: If we don't know if it's a bad guess, and we try to prove it by induction, and we don't see how to prove it, how do we know that means it's wrong? What if we just didn't figure out the right way to prove it?
BRYNMOR CHAPMAN: So the question is if we have a bad guess, and we can't prove it by induction, how do we know that the guess is actually wrong and not that we're doing something suspicious with the proof? So that's a good question. So maybe I should digress here a little bit. If you're trying to figure out a proof or a disproof for a statement that you're not quite sure whether it's true or not, often the thing that you'll want to do is attempt to prove it. see where your proof seems to be breaking, like if you find a block, like something that you can't figure out, and then try and use that to generate a disproof. And then you can iterate on that. And if your disproof gets stuck somewhere, maybe try and use that block to try and come up with a different proof. OK? And eventually, hopefully, you'll be able to come up with one or the other. So in this case, there's a fairly clear path towards a disproof. Put in more numbers. OK. So we could try n equals 4. Then we'd have 64a plus 16b plus 4c plus d should be equal to, what is it, 30? So that's a decent sanity check. Right? Like if that doesn't work, then we know that we've screwed something up. Does that make sense to everybody? Yeah. Question?
AUDIENCE: [INAUDIBLE] How did you decide that those would be the base cases? Is it just for simplicity sake?
BRYNMOR CHAPMAN: So that's because we have four variables here. We've got a, b, c, and d. So we needed four equations, like four constraints. Yeah. Like we could equally well have chosen like n equals 1, n equals 2, n equals 5, n equals 100. It would have given us the correct answer. It just would have taken more complicated computation. Yeah.
AUDIENCE: Sorry. Will there ever be an n over 2 multiplier that works out to be n over 2 [INAUDIBLE]?
BRYNMOR CHAPMAN: Oh, here. Here you mean?
AUDIENCE: Yeah. Or where the next n over 2 would be.
BRYNMOR CHAPMAN: Oh. OK. So the squared term is-- right, because each of these terms here is at least n over 2 squared. The last term is because there are n over 2 of them. And we're trying to evaluate the sum. So we're summing up n over 2 things that are all at least n over 2 squared.
AUDIENCE: What about these 1 plus 2 squared plus 3 squared [INAUDIBLE]?
BRYNMOR CHAPMAN: They're are at least 0. We don't care.
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: Yeah. OK, are people reasonably happy with this? Yeah, OK. So let's move on to a third technique. So sometimes, we're going to end up with sums of sums-- nested summations which we call double sums. So for instance, what if we had the following? So I equals 1 to n of the sum from j equals 1 to i of j. So now, before we had-- the thing inside our sum was this nice simple expression k squared. Now our summand is itself a summation. What can we do about that? How would we evaluate things like this?
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: Yeah, so the answer was to evaluate the inner sum first, figure out a closed form as a function of i, and then we can evaluate the outer sum. So in this case, what do we end up with? What happens when we evaluate this inner sum? I claim that this is something that we already know how to do, something that we've seen before. Yeah?
AUDIENCE: i minus i plus 1 over n?
BRYNMOR CHAPMAN: Yeah, exactly. So this is the sum from i equals 1 to n of i times i plus 1, all divided by 2. Now how could we evaluate this sum? This expression is a little bit more complicated than the ones that we had before. is there a way that we can simplify it? Yeah?
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: Yeah, so let's distribute this i and then break the sum up. So if we distribute this, we end up with i squared plus i divided by 2. And now we've got a sum of a sum. So we can split it into two different summations. i equals 1 to n i squared plus sum of i. So I've taken each of these terms and split it into its own sum and also pulled this factor of 1/2 out in front. So this is now something that we know how to evaluate. We just evaluated it. This is also something we know how to evaluate. Also, we just evaluated it. So this comes out to the answer that we had there, so 1/6 n cubed plus 1/4 n squared plus 1/12 n plus 1/4 times n times n plus 1. Does that make sense to everybody?
Suppose instead we had something similar but slightly different. So sum from i equals 1 to n, sum from j equals i to n. So our inner sum now, instead of going from 1 to i, it's going from i to n. Now we could evaluate this in the same way as we just did. But it turns out that there's a slightly easier way. We can exchange the order of summation. And what I mean by that is that we want the outer sum to be in terms of j and the inner sum to be in terms of i. So what are the possible values of j? So in our-- yes? Yeah?
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: Yeah. So if i equals 1 here, j equals i, j equals 1. So that's the smallest value of j. And j can clearly go up to n. What are the bounds of summation on our inner sum? How would we compute this? What constraints do we have on i and k originally? When we know that 1 is less than or equal to i less than or equal to n i less than or equal to j less than or equal to n. So we could phrase this as 1 less than or equal to i less than or equal to j less than or equal to n. And now we've got bounds on i in terms of j. Does that make sense to everybody? So we still want the sum over the same set of pairs, i and j. We're just expressing it differently. And now our sum n is the same. Does it make sense to everybody how we got this? Yeah?
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: So this just came from the bounds on our inner sum. We're saying that j should range from i up to n. And so then we just stick this pair of inequalities in here. Does that make sense to everybody? Are you reasonably happy with this? So now we've exchanged the order of summation. We've got j for our outer sum, i for our inner sum. And now we've got a much simpler sum here that we can easily evaluate. What is our inner sum?
AUDIENCE: j squared.
BRYNMOR CHAPMAN: Yeah. The sum end has no dependence on the index of summation. So we've just got j terms. All of them are j. So it's j squared. And now this is just the sum that we had before. Does that make sense to everybody? Yeah?
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: This one here? So that's just an expression that you've already seen. We've already seen how to evaluate the sum from j equals 1 to i of j. So that's just plugging in that closed formula for that inner sum. Are people reasonably happy with this? Yeah?
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: Did we? Oh yeah, here-ish. I mean, here it's the particular example where n equals 100. So why don't we move on to the last topic for today? So what happens if we have the following sum? Any idea how we might come up with a closed form for this? Does anybody already know a closed form? Nobody? Really? That's good because it's an open problem. Well, I suppose that doesn't make it good. If you have a closed form, you could a paper about it. That would be pretty exciting. So it turns out that there isn't any nice closed form for this, as far as we know. So does that mean we should just-- hands in the air, give up? Getting some nods. Yeah, I mean, I suppose that's a question of philosophy. But we can still say something about it, right? Maybe we don't need to know exactly what this sum is. But as long as we figure out something, that's close enough, maybe we're still happy. So maybe we want to approximate it. So can anybody give me a guess as to an approximation for this sum?
AUDIENCE: So we were just integrating that as well?
BRYNMOR CHAPMAN: Mm-hmm. So the answer was, again, if we squint really hard and pretend that this is an integral, maybe s is approximately equal to the integral of root x dx, say from 1 to n, which is going to be about 2/3 n to the 3/2. Is that about right? I swear I've done calculus before. It's been a while. So the question then becomes, how close is that approximation? Do we think we're within a factor of 2? Do you think we're off by n by root n? Off by 1 maybe? It's not entirely clear. So in order to figure this out, we're going to use what we call the integral method. So give me a moment to draw this. And redux looks a little bit like that if you squint really hard. So suppose we have a weakly increasing function of x. So root x is indeed weakly increasing, so that'll work. Now, recall Riemann sums from integral calculus. No post-traumatic stress? Are we OK? So how could we approximate the integral of f of x? Yeah?
AUDIENCE: [INAUDIBLE] the right hand [INAUDIBLE].
BRYNMOR CHAPMAN: Yeah. So if we've got 1, 2, 3, 4, dot, dot, dot, we can draw a bunch of rectangles, like this. And this step function here-- actually, maybe I should get a different color. For completeness, maybe I should do that. So this step function here that I've drawn is f of the floor of x. f is weakly increasing. So that means floor of x is an under approximation for x. So f of floor of x is an under approximation for f of x. Now what happens if we integrate this step function? What is the integral from 1 to n of f of floor of x? Yeah?
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: Sorry?
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: Almost. So in this case, it actually-- does it turn out to be s?
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: Yeah, exactly. We're missing a term here. So we can break this into n minus 1 integrals. We've got an interval of width n minus 1. This is constant on each of those width-1 subintervals. So we can break it apart into a whole bunch of rectangles. So this is going to be the sum from i equals 1 to n minus 1 of f of i. Does that make sense to everybody? So we've got intervals of width 1. Our function is constant on each of those intervals. And it's equal to the left-hand side of that interval. Does that make sense to everybody. And this is just going to be s minus f of n. Sorry?
AUDIENCE: Why is n minus 1 the [INAUDIBLE]?
BRYNMOR CHAPMAN: So the question is, why are we using n minus 1 as the bound here? So that's because the width of this interval is n minus 1. We're splitting into n minus 1 intervals of width 1. So for instance, if we went up to, say, n equals 5. So if we were trying to sum f of 1, f of 2, f of 3, f of 4, f of 5, we would then want to compare to this integral here, so the integral from 1 to 5. And this gives us 4 rectangles. We've got the integral from 1 to 2 from 2 to 3, 3 to 4, 4 to 5. And the integral, say, from 2 to 3 has width 1 and height f of 2. So maybe we could phrase this as 1 times f of i. Does that make sense? So we've got an underapproximation for our integral now. So I haven't actually written the integral. So let's let i equal the integral from 1 to n f of x dx. So we said that this function here underapproximates f. So this integral under approximates i. So that tells us that i is greater than or equal to s minus f of n. Now equivalently, we could phrase this as a bound on s in terms of i because s was what we originally wanted to figure out. So instead, we could write this as s is less than or equal to i plus f of n. Does that make sense?
What if, instead, we overapproximated? So now we've got f of the ceiling of x. So the new step function that I've just drawn in green is f of ceiling of x, which is an overapproximation for f of x. So if we integrate it the integral from 1 to n of f of ceiling of x dx should be greater than or equal to i. Now, doing exactly the same thing as we had before, what is this integral? Yeah?
AUDIENCE: Sum from 2 to n of f of i?
BRYNMOR CHAPMAN: Yeah. So sum from i equals 2 to n of f of i-- say times 1-- and this is just s minus f of 1. So s minus f of 1 is at least i. Once again, we can rephrase this as a bound on s in terms of i. So s is greater than or equal to i plus f of 1. So does that make sense to everybody? So putting these together now, we have i plus f of 1 less than or equal to s less than or equal to i plus f of n. So this is what we call the integral bound for increasing functions. Are people reasonably happy with this? So if we go back to our original question where f of x equals root x, what are the bounds we get? What is i first? It wasn't quite what I wrote down before. Yeah?
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: It is from 1 to n. Remember what I wrote originally was a 2/3 n to the 3/2, which is, I believe, the integral from 0 to n. So what we actually have here is i equals the integral from 1 to n of x to the 1/2 dx, which is equal to 2/3 x to the 3/2 evaluated at 1 and n, which is going to be 2/3 times n to the 3/2 minus 1, so almost what we had before. So our lower bound, then, is this value plus f of 1. f of 1 is just root 1. It's 1. And our upper bound is i plus root n. So it turns out that 2/3 n to the 3/2 is a pretty good approximation. It's going to be a little bit larger than that but not much. We're going to be within an additive root n. And given that our approximation is the cube of that, that's actually pretty good. Does that make sense to everybody? Everybody reasonably happy with that?
What if, instead, we had s equals sum from i equals 1 to n of, say, 1 over i? Can we apply our integral bound to this? Who thinks yes? Who thinks no? Can anybody explain why in either direction? Yeah?
AUDIENCE: [INAUDIBLE] but it's going to be [INAUDIBLE], but after 1, it's going to be a convergent [INAUDIBLE] between 1 and 0.
BRYNMOR CHAPMAN: So the answer was after 1, it's going to converge. I would dispute that. Yeah?
AUDIENCE: If I recall correctly, the integral is natural log [INAUDIBLE].
BRYNMOR CHAPMAN: OK, fair enough. So even if we could apply the integral bound, it may not get us very far. I think there's a bigger problem here. Yeah?
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: That's right. So remember that our assumption was that f should be weakly increasing. 1 over i is not, or 1 over x is not. Yeah?
AUDIENCE: Well, at least it's weakly decreasing [INAUDIBLE].
BRYNMOR CHAPMAN: So the observation here is that if we take f of x equals 1 over x, this is weakly decreasing. So we can do something similar. What exactly are we going to do? Well, let's take g of x to be equal to f of n plus 1 minus x. Now what do we know about g? So basically, what we've done here, we are essentially negating the argument. So we're kind of flipping it horizontally. We started with a weakly decreasing function. So when we flip it like this, we're going to end up with a weakly increasing function. Yeah?
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: So are you worried about the n plus 1 as opposed to the n?
AUDIENCE: Yeah, I'm just confused on why you can't do that or how that flips it.
BRYNMOR CHAPMAN: So basically, we are mapping 1 to n and vice versa. And then everything in between should just interpolate linearly. So if we put 1 into here, we end up with f of n. If we put n into here, we end up with f of 1. Does that make sense? So the question is, why do we have the n plus 1 there instead of just an n or a minus x or something like that, which kind of gets into the next question-- what is s in terms of g? So maybe it would be better to write it using ellipses instead of sigma notation. So we defined it as f of 1 plus f of 2, plus dot, dot, dot plus f of n. Now how can we rewrite this in terms of g?
AUDIENCE: p over n plus p over n minus 1.
BRYNMOR CHAPMAN: Yeah. So this is actually equal to the sum of g of i-- same bounds. So now what can we do?
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: Yeah, g satisfies all of the requirements that we needed for our integral bound. So we can apply the integral bound now to g instead of to our original f. So now we know that i plus g of 1 less than or equal to s less than or equal to i plus g of n. So the integral is exactly the same. We've just flipped it. But the area under it is going to be the same. And what is this g of 1? Well, this g of 1 is just f of n. g of n is just f of 1. So this is the integral bound for weakly decreasing f. Does that make sense to everybody? Yeah?
AUDIENCE: Could this also [INAUDIBLE] a negative [INAUDIBLE]?
BRYNMOR CHAPMAN: Strictly speaking--
AUDIENCE: Do we need it to be positive or negative?
BRYNMOR CHAPMAN: So you end up with a slightly different problem if you just negate it, which is-- well, I'll hint at it in a moment. What happens if you take limits as n goes to infinity?
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: Pardon?
AUDIENCE: Oh, it's n goes to infinity.
BRYNMOR CHAPMAN: Yeah, so you have to-- you can do that, but you'd have to adjust for it, and it doesn't work quite as nicely with the limits. So the answer is, strictly speaking, yes, you could negate it if you want to. But flipping it, and-- I personally find it easier to think about. So that was the idea, to negate f instead of x. But segue into the last thing-- we've got a couple of minutes, or eight minutes. Oh, nice. So what about s equals sum from I equals 1 to infinity of, let's say-- because as somebody pointed out, we do not want to be working with logs. So let's say 1 over i squared. So how could we evaluate this infinite sum? Well, we can basically do what we were just doing right. Well, does anybody remember how we actually define what an infinite sum is? It's just going to be a limit of partial sums. Now all of these, we know how to evaluate. So each of these, if we take i sub n to be equal to the integral from 1 to n of 1 over i squared-- sorry, 1 over x squared dx-- what is this integral? Anybody want to evaluate that? No, we don't like calculus? Me too. That's why I'm asking for help. Yeah?
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: Yeah, 1 minus 1 over n. Why are you laughing at me? That's so rude. Oh, come on, guys. So we know what these partial sums are, or we have approximations for these partial sums. So the partial sum s sub n is going to be bounded on one side by-- oops, why don't I write it like this? So i sub n plus f of n less than or equal to s sub n less than or equal to i sub n plus f of 1. Now what happens when we take limits? So weak inequalities are preserved by limits. So the limit of i sub n plus f of n is going to be less than or equal to s, less than or equal to limit of i sub n plus f of 1. Now what does the limit do? Well, we can separate these. What's the limit of i sub n? Yeah?
AUDIENCE: 1 minus infinity or [INAUDIBLE].
BRYNMOR CHAPMAN: 1 minus 1 divided by infinity, basically. So as n goes to infinity, this 1 over n term disappears. So this part is just going to be 1. What's the limit of f of n? Yeah?
AUDIENCE: [INAUDIBLE]
BRYNMOR CHAPMAN: Also infinity.
AUDIENCE: It's also 0.
BRYNMOR CHAPMAN: Yeah, 0. Less than or equal to s less than or equal to-- we just established that this is 1. What's f of 1? 1. So we have an approximation. It's a good one. I'm seeing some people like, yeah, good enough, let's just go home. Some people like, what the hell, we're off by a factor of 2. Yeah, it's between 1 and 2-- not so great. Any ideas how we could make it better? How can we make our bounds more precise? Maybe if we go back to the picture, it'll be a little bit easier to see. This lack of precision is coming from the fact that we're looking at the difference between these two step functions. So the farther apart they are, the worse our approximation is going to be. So if we just forget about the first few terms, compute those exactly, and then just approximate the rest, we're going to end up with a more precise bound. So if, instead, we say, s equals 1 plus 1/4 plus 1/9 plus the sum from i equals 1 to infinity of 1 over i plus 3 squared-- sorry, it's a bit crowded. Now, what happens if we approximate this sum? How close are we going to get? Well, our error term, remember, was just the first term in our series. We are going to be between the integral and the integral plus the first term. Here, the first term is much smaller. So this time, we've got-- what is it? 1 over 16. So instead of being between i and i plus 1, we're now between i and i plus 1 over 16 for a different i-- same i? No, different i. Does that make sense to everybody? So if you want a better approximation, just strip some terms of the front and approximate the tail of the sum instead of the entire thing. So that's all we have time for today. Let's see. I'm not sure if we we'll see you next week. Somebody will see you next week. Zach we'll see you next week. Feel free to come up if you have any questions. Yeah?