Placeholder Image

字幕表 動画を再生する

  • PROFESSOR: The following content is provided under a Creative

  • Commons license.

  • Your support will help MIT OpenCourseWare

  • continue to offer high quality educational resources for free.

  • To make a donation or view additional materials

  • from hundreds of MIT courses, visit MIT OpenCourseWare

  • at ocw.mit.edu.

  • Today we're going to start with a simple problem

  • that many of you may have already encountered.

  • For example, when you got a student loan

  • or if your family took a loan out on your house,

  • you know, a home mortgage loan, and it's the problem

  • of pricing an annuity.

  • An annuity is a financial instrument

  • that pays a fixed amount of money

  • every year for some number of years,

  • and it has a value associated with it.

  • For example, with a student loan,

  • the value is the amount of money they gave you to pay MIT,

  • then later in life-- every year or every month-- you're

  • going to send them a check.

  • And you want to sort of equate those two things to find out,

  • are you getting enough money for the money

  • you're going to pay back monthly sometime in the future?

  • So let's define this, and there's a lot of variations

  • on annuities, but we'll start with one that's called

  • an n-year $m-dollar payment annuity,

  • and it works by paying m dollars at the start of each year,

  • and it lasts for n years.

  • Now, usually n is finite, but not always,

  • and in a few minutes we'll talk about the case

  • when it's infinite.

  • But this includes home mortgages,

  • where you pay every month for 30 years.

  • Megabucks, the lottery.

  • They don't actually give you the million dollars.

  • They give you $50,000 per year for 20 years,

  • and call it a million bucks.

  • Retirement plans.

  • You pay in every year, and then you

  • get some big lump sum later.

  • Life insurance benefits, you know, and so forth.

  • Now, if you go to Wall Street, this is a big deal.

  • A lot of the stuff that happens on Wall Street

  • involves annuities in one form or another,

  • packaging them all up and, in fact, we'll

  • look at later when we do probability.

  • It was how these things were packaged and sold

  • that led to the sub-prime mortgage disaster,

  • and we'll see how some confusion over independents, when

  • you look at random variables, led to the global recession,

  • a real disaster.

  • Of course, some people understood how all that worked,

  • made hundreds of billions of dollars at the same time.

  • So it was sort of money went from one place to another.

  • So it's pretty important to understand

  • how much this is worth.

  • What is this instrument-- a piece

  • of paper that says it will pay you

  • m dollars at the beginning of each year for n years, what

  • is that worth today?

  • For example, say I gave you a choice--

  • the Megabucks choice-- $50,000 a year

  • for 20 years or a million dollars today.

  • How many people would prefer the $50,000 a year for 20 years?

  • A few of you.

  • How many would prefer the million bucks right up front?

  • Much better.

  • OK.

  • Always better to have the cash in hand,

  • because there's things like inflation--

  • pretty low now-- interest.

  • You can put the money in the bank

  • or invest it and make some money hopefully.

  • So the million dollars today is a lot better,

  • which is why the State pays you 50 grand a year for 20 years.

  • It's better for them, and they call it a million bucks.

  • So that was pretty clear, but what

  • if I gave you this option-- 700 grand today or 50 grand a year

  • for 20 years?

  • How many people want the cash upfront-- 700 grand only.

  • A few.

  • How many people want 50 grand a year for 20 years?

  • All right, we're almost-- that's pretty close to half way.

  • How about 500 grand today versus 50 grand a year for 20 years?

  • How many want half a million today?

  • A lot of people like the cash.

  • You know, it's this kind of a time, you have the recession,

  • it's a disaster on Wall Street.

  • You know, Street Wall Street didn't like the cash.

  • How many want, instead of a half a million

  • up front, 50 grand a year for 20 years?

  • All right, now we're about halfway.

  • All right, well that's pretty good.

  • So we're going to find out what you should pay,

  • or at least one way of estimating that.

  • Now, to do that, we've got to figure out what

  • $1 today is worth in a year.

  • And to do that, we make an assumption,

  • and the assumption is that there's

  • a fixed-- we'll call it an interest rate.

  • It's sort of the devaluation of the money per year.

  • And we're going to call it p.

  • Later we'll plug in values for p,

  • but you can think of it as like 6%, 1%.

  • You know, it's the money, if you put money in a bank,

  • they'll give you some percent back every year.

  • And, of course, the fact that different people

  • have different ideas of what this would be,

  • allows people to make money on Wall Street.

  • As we'll see, a slight difference in p

  • can make big differences in what the annuity is worth.

  • So for example, $1 today is going to equal 1 plus p

  • dollars in one year.

  • Similarly, $1 today-- how much is that

  • going to be worth in two years?

  • Say that p stays fixed, the same over all time.

  • One plus p squared, because every year you

  • multiply what you got by 1 plus p, because that's

  • the interest you're getting.

  • All right, we'll think of it in terms of interest.

  • In three years, $1 today is worth 1 plus p cubed in

  • three years and so forth.

  • All right.

  • Now, what we really care about is what's $1, or m dollars,

  • worth today if you're getting it next year?

  • So we need to sort of flip this back the other way.

  • So what is $1 in a year worth today in terms of p?

  • So if I'm going to be paid $1 in a year,

  • what would be the equivalent amount to be paid today?

  • One over 1 plus p, because what's happening here

  • is, as you go forward in a year, you just multiply by 1 plus p.

  • So 1 over 1 plus p turns into $1 in a year-- being

  • paid in a year.

  • All right.

  • What is $1 a year in two years worth today?

  • One over 1 plus p squared.

  • So $1 in two years is worth this much today.

  • Well, now we can use this to go figure

  • out the current value of that annuity.

  • We just figure out what every payment is worth today and then

  • add it up.

  • So we'll put the payments over here,

  • and we'll compute the current value

  • of every payment on this side.

  • So with the annuity, the way we've

  • set it up is it pays n dollars at the start of every year,

  • so the first payment is now.

  • So the first of the n payments is now,

  • and since it's being paid now, that's worth m dollars.

  • There's no devaluation.

  • The next payment is m dollars in one year,

  • and so that's going to be worth m over 1 plus p today.

  • And the next payment is m dollars in two years.

  • That's worth m over 1 plus p squared,

  • and we keep on going until the last payment.

  • It's the n-th payment, so it's m dollars in n minus 1 years.

  • And so that's going to be worth m over 1 plus p

  • to the n minus 1.

  • All right.

  • So we can compute the current value of all those payments,

  • then the annuity is computed-- the value is computed just

  • by adding these up, of all the current values.

  • So the total current value is the sum i equals 0 to n minus 1

  • of m over 1 plus p to the i.

  • And that is the total current value.

  • That's what you should pay today for the annuity.

  • Any questions?

  • What we did here?

  • All right.

  • Well, of course, what we'd like is a closed form expression

  • here.

  • Something that's simple so we could actually

  • get a feel without having to add up all those terms,

  • and that's not hard to get.

  • In fact, let's put this sum in a form

  • that might be more familiar.

  • This equals-- we'll pull the m out in front--

  • and let's use x to be 1 over 1 plus p to the i.

  • And so x equals 1 over 1 plus p, and I wrote it this way

  • because this might be familiar.

  • Does everybody remember that from-- I think

  • it was the second recitation?

  • Anybody remember the formula?

  • What this evaluates to?

  • The sum of x to the i, where i goes from 0 to n minus 1?

  • Remember that?

  • One minus x to the n.

  • Remember 1 minus x.

  • In the second recitation, I think,

  • we proved that this equals that.

  • What was the proof technique we used?

  • Induction.

  • OK?

  • So, in fact, there's a theorem here.

  • For all n bigger and equal to 1 and x not equal to 1,

  • we proved the sum from i equals 0 to n minus 1 x to the i

  • equals 1 minus x to the n over 1 minus x.

  • And so this is a nice, closed form.

  • No sum any more, just that, which is nice.

  • Now, induction proved it was the right answer.

  • Once you knew it-- we gave it to you-- using induction

  • to prove that theorem wasn't hard.

  • What we're going to look at doing this week and next week

  • is figuring out how to figure out this

  • was the answer in the first place.

  • Methods for doing that-- to evaluate the sum-- and there's

  • a lot of ways that you can do that particular sum.

  • Probably the easiest is known as the perturbation method.

  • This sometimes works.

  • Certainly with sums like that, it often works.

  • The idea is as follows.

  • We're trying to compute the sum S, which is 1

  • plus x plus x squared plus x to the n minus 1,

  • and what we're going to do is perturb it a little bit

  • and then subtract to get big cancellation.

  • In this case, it's pretty simple.

  • We multiply the sum by x to get x plus x squared plus-- I've

  • defined S to be that, x times S-- well, I

  • get x plus x squared and so forth, up to x to the n,

  • and now I can subtract one from the other and almost everything

  • cancels.

  • So I get 1 minus x times S equals 1.

  • These cancel, cancel, cancel.

  • Minus x to the n.

  • And therefore S equals 1 minus x to the n over 1 minus x.

  • So that's a vague method.

  • This gets used all the time in applied mathematics,

  • and they call it the perturbation method.

  • Take your sum, wiggle it around a little bit,

  • get something that looks close, subtract it,

  • everything cancels, life is nice,

  • and all of a sudden you've figured out the answer.

  • So getting back to our annuity problem,

  • we can plug that formula back in here.

  • So the value of the annuity is m times 1 minus x to the n

  • over 1 minus x.

  • We'll plug in x equals 1 over 1 plus p,

  • and we get m 1 minus 1 over 1 plus p

  • to the n over 1 minus 1 over 1 plus p, just plugging in.

  • And now to simplify this, I'll multiply the top and bottom

  • by 1 plus p, and I'll get 1 plus p minus 1 on the bottom.

  • Just gives me a p on the bottom.

  • I have a 1 plus p on the top minus 1 over 1

  • plus p to the n minus 1, all over p.

  • So now we have a formula-- closed form expression

  • formula-- for the value of the annuity.

  • All's we've got to plug in is m, the payment every year,

  • n, the number of years, and then p, the interest rate.

  • And so, for example, if we made m be $50,000,

  • as in the lottery.

  • We made n be 20 years, and say we took 6% interest, which

  • is actually very good these days, and I plug those in here,

  • the value is going to be $607,906.

  • All right.

  • So those of you that preferred 700 grand-- if you assume 6%

  • interest-- you're right.

  • Those of you who preferred 500 grand, no,

  • you're better off waiting and getting your 50 grand a year.

  • Now, of course, if the interest rate is lower,

  • well, that changes things.

  • That shifts it even more.

  • The annuity is worth even more if the interest rate is lower--

  • if p is smaller.

  • In fact, say p was 0.

  • Say the interest rate is 0, so $1 today equals $1 tomorrow,

  • then what is the lottery worth?

  • A million dollars.

  • And the bigger p gets, the less your payment is worth.

  • Any questions about that?

  • OK.

  • What if you were paid $50,000 a year forever-- you live forever

  • or it goes to your estate and your heirs,

  • $50,000 a year forever or a million dollars today.

  • How many people want the million dollars today?

  • How many want 50 grand a year forever?

  • Sounds good.

  • You know, that's an infinite amount of money, sort of.

  • It's not as good as it sounds.

  • Let's see why.

  • So this is a case where n equals infinity,

  • and so I'll claim that if n equals infinity,

  • then the value of this annuity is just m times 1

  • plus p over p.

  • Let's see why that's the case.

  • You know, it sounds hard to evaluate,

  • because it's an infinite number of payments,

  • but what happens here when n goes to infinity?

  • What happens to this thing?

  • That goes to 0 as n goes to infinity,

  • as long as p is bigger than 0.

  • So we're going to assume 6% interest.

  • So that goes away, so the annuity is worth just

  • that, m times 1 plus p over p, because the limit as n

  • goes to infinity of 1 over 1 plus p to the n minus 1,

  • that's going to 0.

  • So the value for m is $50,000, and at 6% V is only $883,000.

  • So you're better off taking a million dollars

  • today than $50,000 a year forever.

  • Now, if you think about it, and think about it

  • as an interest rate, why should it

  • be obvious that you're better off with a million dollars

  • today than 50 grand a year forever?

  • Think about what you could do with that million dollars

  • if you had it today at 6% interest.

  • What would you do with it to make more money than 50 grand

  • a year forever?

  • Yeah.

  • AUDIENCE: You could have like-- you could make $50,000 per year

  • just off of [INAUDIBLE].

  • PROFESSOR: Yeah.

  • In this model, if the interest rate is 6%,

  • you can put in the bank.

  • It makes 6% every year, that's 60 grand a year forever.

  • Better than 50 grand a year forever.

  • So maybe it's-- even without doing the math,

  • you can tell which way it's going to go,

  • but this tells you exactly what it's worth.

  • Any questions?

  • OK.

  • Yeah.

  • AUDIENCE: [INAUDIBLE] current value--

  • that's how much it's worth to you right now.

  • PROFESSOR: Yeah.

  • AUDIENCE: So and, like, if you have $1 in the future--

  • PROFESSOR: Yeah.

  • AUDIENCE: --where S right now is m over 1 plus p--

  • PROFESSOR: Yeah.

  • AUDIENCE: --is it worth less to you [INAUDIBLE] then later on,

  • it's going to be worth more to you.

  • PROFESSOR: Ah, so if you move yourself

  • forward in time, $1 a year, in a year it'll worth $1 to you--

  • AUDIENCE: Yeah.

  • PROFESSOR: --but today it's worth less than $1 to you,

  • because you could take the dollar today and invest

  • in the bank, and it's worth more in a year, because the money

  • grows in value, as a way to think of it,

  • because you can earn interest on it.

  • What's that?

  • AUDIENCE: You could spend it.

  • PROFESSOR: Yeah.

  • Yeah, if you just spend it, well,

  • then at least you had the use of what

  • you spent it on for the year.

  • So there's some other kind of value, right?

  • Maybe you bought a house or something

  • that-- maybe something that even appreciated in value.

  • OK.

  • But these things get sort of squishy,

  • and that is where a lot of people

  • make money on Wall Street, is because different companies

  • have different needs for money.

  • They have different views of what the interest rates are

  • going to be, and you can play in the middle

  • and make a lot of money that way.

  • So more generally, there's a corollary to the theorem,

  • and that is that if the absolute value of x is less than 1,

  • then the sum i equals 0 to infinity x to the i

  • is just 1 over 1 minus x.

  • We didn't prove this back in the second recitation,

  • because there's no n to induct on here,

  • but the proof is simple from the theorem.

  • And it's simply because if x is less than 1,

  • an absolute value, as n goes to infinity, that goes to 0,

  • and so you're just left with 1 over 1 minus x.

  • So, for example, what's this sum?

  • This one you all know, I'm sure.

  • Out to infinity.

  • What's that sum to?

  • To 2.

  • Yeah.

  • It's 1 over 1 minus 1/2, which is 2.

  • What about this sum out to infinity?

  • What does that sum to?

  • AUDIENCE: [INAUDIBLE]

  • PROFESSOR: Yeah, 3/2, 1 over 1 minus 1/3 is 3/2.

  • So, easy corollaries.

  • These are all examples of geometric series.

  • That's what a definition of a geometric series is.

  • Something that's going down by a fixed-- each term

  • goes down by the same fixed amount every time.

  • And geometric series, generally sum

  • to something that is very close to the largest term.

  • In this case, it's 1.

  • Very common, because of that formula.

  • It's 1 over 1 minus x.

  • Any questions about this or geometric series?

  • All right.

  • Well, those are straight geometric sums.

  • Sometimes you run into things that are a little bit more

  • complicated.

  • For example, say I have this kind of a sum, i equals 1 to n,

  • i times x to the i.

  • Now, those are adding up x plus 2x squared plus 3x cubed,

  • and so forth, up to n x to the n.

  • You know, that's a little more complicated.

  • The terms are getting-- decreasing

  • by a factor of x, increasing by 1 in terms of the coefficient

  • every time.

  • A little trickier.

  • So say we wanted to get a closed form expression for that?

  • There are several ways we can do it.

  • The first would be to try to use perturbation-- the perturbation

  • method.

  • Let's try that.

  • So we write S equals x plus 2x squared plus 3x cubed plus nx

  • to the n, and let's try the same perturbation.

  • Multiply by x, I get that x squared

  • plus 2x cubed plus n minus 1x to the n, plus nx to the n plus 1.

  • And then I subtract to try to get all the cancellation.

  • So then I do that.

  • I get 1 minus x times S. Well, I didn't quite cancel everything.

  • X plus x squared plus x cubed plus x

  • to the n plus n-- or minus nx to the n plus 1.

  • Ah, it didn't quite work.

  • Anybody see a way that I can fix this up?

  • What about this piece?

  • That's still a mess here.

  • Can I simplify that?

  • Yeah?

  • AUDIENCE: [INAUDIBLE]

  • PROFESSOR: Yeah.

  • There's

  • a simpler way.

  • Yeah.

  • AUDIENCE: That's a geometric series.

  • PROFESSOR: That's a geometric series.

  • We just got the formula for it, so that's easy.

  • This equals 1 minus x to the n over 1 minus x minus the 1,

  • because I'm missing the 1 here.

  • So we can rewrite this whole thing over here.

  • Oops.

  • Yikes.

  • Got attacked.

  • What's that?

  • AUDIENCE: Would it be 1 minus x should be n plus 1?

  • PROFESSOR: Yes it would.

  • That's right.

  • I've got to add 1 to there.

  • OK.

  • So that's good.

  • So that says that 1 minus x times S

  • equals 1 minus x to the n plus 1 over 1 minus x minus 1,

  • and then I've got to remember to subtract that term too.

  • Minus nx to the n plus 1.

  • That means now I just divide through,

  • and I simplify-- divide through by 1 minus x-- and simplify,

  • and I get the following formula.

  • I won't go through all the details, but it's not hard.

  • Let's see if I got that right.

  • Yeah, that looks right.

  • OK, so that is the closed form expression

  • for that sum, which we can get from the perturbation

  • method and the fact that we'd already

  • done the geometric series.

  • There's another way to compute these kinds of sums,

  • which I want to show you, because it can be useful.

  • So we're going to do the same sum and derive the formula

  • a different way.

  • This method is called the derivative method,

  • and the idea is to start with a geometric series which

  • it's close to and then take a derivative.

  • So for x not equal to 1, we already know from the theorem

  • that i equals 0 to n, x to the i equals 1 minus x to the n

  • plus 1 over 1 minus x.

  • That was the theorem.

  • We already know that.

  • Now, I can take the derivative of both sides,

  • and let's see what we get by taking the derivative.

  • Well, here I get the sum.

  • The derivative of x to the i is just i times x to the i

  • minus 1.

  • The derivative over here is a little messier.

  • I've got to have-- well, I take 1 minus x

  • times a derivative of that.

  • Derivative of this is now minus n plus 1, x to the n.

  • Then I take this times the derivative of that

  • is now minus minus 1, 1 minus x to the n plus 1,

  • and then I divide by that squared.

  • Now, when we compute all that out, we get this, 1 minus n

  • plus 1, x to the n plus nx to the n plus 1 over 1

  • minus x squared.

  • I won't drag you through the algebra,

  • but it's not hard to go from there to there.

  • This is pretty close to what we wanted.

  • We're trying to figure out this, and we almost got there.

  • What do I do to finish it up?

  • AUDIENCE: Multiply by x.

  • PROFESSOR: Multiply by x.

  • Good.

  • So if I take this and multiply by x, i equals zero to n,

  • ix to the i equals x minus n plus 1, x to the n plus 1,

  • plus nx to the n plus 2, all over 1 minus x squared.

  • OK?

  • Which should be the same-- yeah-- the same formula

  • we had up there.

  • So that's called the derivative method.

  • You can start manipulating-- you treat these things

  • as polynomials-- these sums-- and you start manipulating them

  • like you would polynomials.

  • In fact, there's a whole branch of mathematics

  • called generating functions that we won't have time

  • to do in this class that's in chapter 12 of the text.

  • But you do things like that to get sums.

  • Any questions about what we did there?

  • You can also do a version where you take integrals of this

  • if you want, and then you get the i's

  • in the denominator instead of those coefficients.

  • For homework, I think we've given you

  • the sum of i squared x to the i.

  • How do you think you're going to do that?

  • Any thoughts about how you're going to solve that?

  • Get the sum, a closed form for the sum of i

  • squared x to the i?

  • AUDIENCE: Do the derivative method twice.

  • PROFESSOR: Yeah, do it twice.

  • Take this, which now you know.

  • Take the derivative again.

  • Won't be too hard.

  • You can also take the version of this where n goes to infinity.

  • Let's do that.

  • If the absolute value of x is less than 1, the sum i

  • equals 1 to infinity of ix to the i, what does that equal?

  • This one, you can see it easier up here.

  • What happens when n goes to infinity?

  • What does this do?

  • X is less than 1, an absolute value.

  • What happens to this as n goes to infinity?

  • This term.

  • Goes to 0, right?

  • This gets big, but this gets smaller faster.

  • What happens to this term as n goes to infinity?

  • Same thing, 0.

  • All I'm left with is x over 1 minus x squared.

  • Now, this formula is useful if you're

  • trying to, say, get the value of a company,

  • and the company is growing.

  • Every year the company grows its bottom line by m dollars.

  • So the first year, the company generates m dollars,

  • the next year it generates two m dollars in profit,

  • the next year is three m dollars.

  • So you've got an entity that every year

  • is growing by a fixed amount.

  • It's not doubling every year, but every year

  • adds in m dollars more of profit.

  • What would you pay to buy that company?

  • What is that worth?

  • So you can think of this as, again, an annuity.

  • Here the annuity pays im dollars, in this case,

  • at the end, not the beginning, say, of the year i forever.

  • This company is-- or this annuity-- is worth, well,

  • we just plug into the formula.

  • Instead of $1 each year, it's m so there's an m out front.

  • x is 1 over 1 plus p, and then we have 1 minus 1 over 1

  • plus p squared.

  • And if we multiply the top and bottom by 1 plus p squared,

  • we get m 1 plus p over p squared.

  • So it's possible with a very simple formula

  • to figure out how much you should

  • spend to buy this company, what its value is today.

  • So, for example, say the company was adding $50,000 a year

  • in profit.

  • The interest rate was 6%, the value of this company

  • is $14 million-- $14.7 million, just plugging

  • into that formula.

  • So people that buy companies and stuff,

  • they use formulas like this to figure out what it's worth.

  • Of course, you've got to make sure

  • it's really going to keep paying the $50,000 more every year

  • and that this is the right interest rate

  • to be thinking about.

  • You know, and the guys on Wall Street--

  • the bankers on Wall Street-- they all

  • have their estimations for what these things are--

  • the value of p they would put into these formulas.

  • Any questions about that?

  • Yeah.

  • AUDIENCE: [INAUDIBLE]

  • PROFESSOR: OK.

  • Good.

  • So this one is OK?

  • OK.

  • I plugged x equals 1 over 1 plus p,

  • like we did before-- remember for the annuity--

  • because every year you're degrading it,

  • devaluing by 1 over 1 plus p.

  • So that's the x term, and it's paying-- in the i-th year,

  • it's paying im dollars.

  • All right?

  • So the first year it pays n dollars, the next year 2 m,

  • the next year 3 m, the next year 4 m,

  • but every year you're knocking it down by 1 plus 1

  • over p to the number of years.

  • So what you get-- the sum you've really got here--

  • is i equals 1 to infinity, im dollars are paid,

  • but those dollars are worth 1 over 1 plus p

  • to the i today, the current value.

  • That's a good question.

  • I should've said that.

  • That's a great question.

  • So that's how we connected this up,

  • because you're getting paid this much in our years,

  • and that's worth that much degradation

  • or that much devaluation today, and now we

  • add up a total current value.

  • So even a company that is paying you more and more

  • every year still has a finite value, because the extra--

  • the payments are increasing but only linearly.

  • The value today is decreasing geometrically,

  • and the geometric decrease wipes out the value

  • of the company in the future.

  • Yeah.

  • AUDIENCE: Are you [? squaring ?] quantity of [INAUDIBLE].

  • PROFESSOR: What did I do?

  • Oh, wait, wait, wait.

  • I screwed up here too.

  • Is that what you're asking about?

  • Yeah.

  • That's what I should have done, right?

  • Because I got 1 minus x is 1 minus 1 over 1 plus p.

  • That gets squared, and now when I multiply 1 plus p squared,

  • it's multiplying this by 1 plus p.

  • It's 1 plus p minus 1 is p.

  • So I have p squared.

  • All right, so this part's OK.

  • That part I wrote wrong.

  • That's good.

  • Any other questions?

  • So let's do a simple example.

  • What is this sum?

  • A 1/2 plus 2/4 plus 3/8 plus 4/16 forever.

  • What's that sum equal?

  • You can plug that in the formula.

  • AUDIENCE: [INAUDIBLE]

  • PROFESSOR: Yeah.

  • That's right.

  • Good.

  • These details.

  • Otherwise that sum would be what?

  • If I didn't put the negative here,

  • it's going to be infinity, and that's not so interesting.

  • The negative makes it more interesting, so I got 1 over 2

  • to the i in there.

  • What's it worth then?

  • Well, I can plug in the formula.

  • What's x?

  • One half.

  • So I get 1/2 over 1 minus 1/2 squared is 1/2 over 1/4,

  • and that's 2.

  • Any questions on that formula?

  • It's amazing how useful these things get to be later.

  • So that's sort of the geometric kinds of things.

  • Next I want to talk about more of the arithmetic kinds of sums

  • and what you do there.

  • In fact, we've already seen one that we've done.

  • If I sum i equals 1 to n of i-- I think we've already

  • done this one-- that's just n times n plus 1 over 2,

  • and probably most of you even learned

  • that formula back in middle school,

  • I'm guessing-- maybe before.

  • How many people know the answer for this sum?

  • The sum of the squares-- the first n squares.

  • Somebody knows.

  • What is it?

  • AUDIENCE: n times n plus 1 times 2n plus 1, all over 6.

  • PROFESSOR: Very good.

  • That is correct.

  • Most people don't remember that one.

  • It's a little harder to derive.

  • How would you prove this by induction?

  • Unfortunately, induction doesn't tell you

  • how to remember what the formula was,

  • and there's a couple of ways you can go about that.

  • One is, you can remember or guess

  • that the answer is a polynomial in n.

  • In fact, because you're summing squares,

  • you might guess that it's a cubic polynomial in n,

  • and if you remember just that or guess just that, then you

  • could actually plug in values and get the answer.

  • And this is-- you know, a common method

  • of solving these sums is you sort of guess

  • the form of the solution.

  • In this case you might guess that for all n,

  • the sum i equals 1 to n of i squared equals a cubic.

  • And then what you would do is plug in the value n equals 1,

  • n equals 2, maybe even-- we'll make

  • it n equals 0-- make it simple and start

  • getting some constraints on the coefficients.

  • If you would plug in n equals 0, the sum is 0.

  • The polynomial evaluates to d.

  • That tells you what d has got to be right away. n equals 1.

  • The sum is 1, and when you plug into the polynomial,

  • you get a plus b plus c plus d.

  • n equals 2.

  • Well, that's 1 plus 4 is 5, 2 cubed is 8,

  • so you have 8a plus 4b plus 2c plus d,

  • and you'll need one more since you've got four variables.

  • Let's see, 1 plus 4 plus 9 is 14.

  • I've now got 3 cubed is 27a plus 9b plus 3c plus d.

  • So now I've got four equations and four variables

  • and, with any luck, I can solve that system of equations

  • and get the answer.

  • And, in fact, you can.

  • When you solve this system, you get a equals 1/3, b equals 1/2,

  • c equals 1/6, and d equals 0.

  • And that's exactly what you get in that formula.

  • So that's a way to reproduce the formula if you forgot it.

  • Now, this method-- really to be sure you

  • got the right answer-- you've got to go prove it

  • by induction, because I derived the answer-- if it

  • was a polynomial, I would have gotten it right,

  • but I might be wrong in my guess.

  • And to make sure your guess is right,

  • you've got to go back and use induction

  • to prove it for this approach.

  • Yeah.

  • AUDIENCE: How do you know that it would be [INAUDIBLE] and not

  • some higher power?

  • PROFESSOR: Well, it turns out that anytime you're

  • summing powers, the answer is a polynomial to one

  • higher degree.

  • So if you just remembered that fact, or you guessed that fact.

  • Another way to sort of imagine that might be true

  • is that I'm getting n of them, so I

  • might be multiplying-- the top one is n squared,

  • so I'm going to have n of them about n squared.

  • Might be something like n cubed.

  • That's another way you could think of it, to guess that.

  • Any other questions on this?

  • So far, all these sums had nice closed forms, and a lot of them

  • do that you'll encounter later on, but not all,

  • and sometimes you get sums that don't have a nice closed form--

  • at least nobody has ever figured out one,

  • and probably doesn't always exist.

  • For example, what if I want to sum the first n

  • square roots of integers?

  • Let's write that down.

  • So say I want a closed form for this guy.

  • Nobody knows an answer for that, but there

  • are ways of getting very good, close bounds on it that

  • are closed form, and these are very important,

  • and we're going to use this the rest of today

  • and the rest of next time.

  • And they're based on replacing the sum with an integral,

  • and the integral is very close to the right answer,

  • and then we can see what the error terms are.

  • So let's first look at the case when

  • we've got a sum where the terms are increasing as i

  • grows, and we'll call these integration bounds,

  • and a general sum will look like this-- i equals 1 to n

  • of f of i, and the first case is when f is a positive increasing

  • function, increasing in i.

  • Integration bounds, and so we're increasing function.

  • So let me draw a picture that will hopefully

  • make the bounds that we're going to get pretty easy.

  • So let's draw the sum here as follows.

  • I've got 0, 1, 2, 3, n minus 2, n minus 1, n,

  • and draw the values of f here.

  • Here's f of 1, f of 2-- it's increasing-- f of 3,

  • f of n minus 1, and f of n.

  • Then I'll draw the rectangles here.

  • So this has area of f of 1, this has area f of 2,

  • this has area f of 3, and we keep on going.

  • Let's see, this will be f of n minus 2

  • on this one-- I'll just do f of n minus 1, draw this guy here.

  • So its unit width, its height is f of n minus 1,

  • so its area is f of n minus 1, and then f of n.

  • And let me also-- so the sum of f of i

  • is the areas in the rectangles.

  • That's what the sum is, and I want

  • to get bounds on this sum using the integral,

  • because integrals are easier to compute.

  • So let's draw the function f of x from 1 to n.

  • All right, so this is f of x as a function.

  • Now I claim that the sum i equals 1 to n of f of i

  • is at least f of 1 plus the integral from 1 to n,

  • f of x, dx.

  • Now, the integral from 1 to n of f of x

  • is this stuff, the stuff under the curve.

  • It comes down here, starts at 1, and it's

  • the stuff under the curve.

  • And what I'm saying here is that if you

  • take that stuff under the curve and add

  • f of 1, which is this piece, that's

  • a lower bound on our sum.

  • The sum's bigger than that.

  • So what I'm saying is the area in the rectangles

  • is at least as big as the area in the first rectangle

  • plus the area under the curve.

  • Does everybody see why that is?

  • I'm saying the sum is the area in the rectangles, right?

  • That's pretty clear.

  • And that is at least as big as the first rectangle f of 1

  • plus the stuff under the curve, which is the integral,

  • and I've left-- I've chopped off these guys.

  • That's extra.

  • OK?

  • Is that all right?

  • So lower bound.

  • Any questions on the lower bound?

  • This is a picture proof, which we always tell you not to do,

  • but we're going to do one here.

  • And, of course, it totally hides why did I need f is increasing,

  • but we'll see that in a minute.

  • The proof would not work unless it is increasing here.

  • Any questions, because now going I'm

  • going to do the other bound, the other side.

  • I also claim-- this will be a little trickier to see--

  • that the sum is at most f of n plus the integral from 1 to n.

  • So this is the lower bound add in f of 1,

  • the upper bound just add in f of n.

  • So let's see why that's true.

  • Now, to see that, this is-- I'm not

  • going to be able to draw it.

  • I want you to imagine taking this curve and the area

  • under it, down to here, and sliding it left one unit.

  • sliding it left to here, sliding it left one unit over to here.

  • Now, when I slide it left one unit, did the area under it

  • change?

  • No.

  • It's the same area under it, just where

  • it sits on the picture is now out here.

  • It's this area under this guy, but it's the same thing,

  • its the same integral.

  • And you can see that it's more than what's

  • in these rectangles, because I got all this stuff.

  • And, of course, I didn't even include this,

  • so now I add the f n.

  • So if I take the area under the curve, which is the integral,

  • shift it left one, so it only goes up

  • to here now, and then add in this rectangle, that dominates

  • the area in the rectangles.

  • Bigger than.

  • Do you see that?

  • I could do a lot of equations on the board

  • but, for sure, that would be hopeless to follow.

  • Any questions about this?

  • Yeah.

  • AUDIENCE: I guess I understand the lower amounts because we're

  • cutting off the triangles.

  • PROFESSOR: Yeah.

  • But is there-- is it a lot of hand waving,

  • or am I just missing something, that it's always going to be

  • the f of n is what we--

  • PROFESSOR: Yeah.

  • There's a little hand waving going on,

  • but I do believe it is true.

  • With equations you can make it precise.

  • Let's look at it again, do this one more time.

  • AUDIENCE: [INAUDIBLE]

  • PROFESSOR: Yeah, I'm waving hands a little bit,

  • but it also-- hopefully the intuition comes across,

  • because when I shift left by one,

  • this point becomes this point, and that point becomes

  • that point, and I'm catching sort

  • of the cusp of these rectangles, and now I take this curve here,

  • shifting the whole curve left one unit,

  • and the area doesn't change.

  • It would be equivalent of taking the integral from 0

  • to n minus 1.

  • You notice what I'm doing-- of f of x plus 1.

  • There's another way to look at it mathematically,

  • maybe-- probably the formal way to do it--

  • but the idea is that this now contains

  • all these first n minus 1 rectangles,

  • are contained underneath it.

  • And then I just add this in, and I'm good to go.

  • I've contained all the rectangles now

  • for the upper bounds.

  • All right, mathematically what this

  • is, this curve is 0 to n minus 1,

  • fx plus 1, which is the same thing as what that is.

  • Any questions for that?

  • But now I have good bounds on the sum.

  • We know that the sum is at least this and at most that,

  • and those two bounds only differ by a single term in the sum,

  • so they're very close.

  • These actually are good formulas to write down

  • for your crib sheet.

  • That is worth doing on the test, and we'll use them more today,

  • and we'll also use them on Thursday.

  • So now we can actually get close bounds

  • on the sum of the square roots.

  • So let's see how this works for f

  • of i equal to the square root of i, which is increasing.

  • So I compute the integral from 1 to n of square root of x dx,

  • and that's just x to the 3/2 over 3/2, evaluated at n and 1,

  • and that just equals 2/3 n to the 3/2 minus 1.

  • And now I can compute the bounds on the sum

  • of the first n square roots.

  • So I know that square root i equals 1 to n-- well,

  • the upper bound is f n plus the integral,

  • and the lower bound is f of 1 plus the integral.

  • What is f of n?

  • That's the square root of n.

  • What is f of 1?

  • The square root of 1, which is 1.

  • So I'll plug that in here.

  • I get 2/3 n to the 3/2 plus 1 minus 2/3 is plus 1/3,

  • and here I get 2/3 n to the 3/2 plus the square root

  • of n minus 2/3.

  • So now I have pretty good bounds on the sum of the first n

  • square roots using this method.

  • So for example, take n equals 100.

  • This number evaluates to 667.

  • This number evaluates to 676, and the difference

  • is 9, which is the square root of 100 minus 1.

  • This is the square root of n, this is 1,

  • so the gap here, square root of n minus 1, and n equals 100.

  • Square root of 100 minus 1 is 9, so I shouldn't be

  • surprised my gap here is nine.

  • So I didn't get exactly the right answer,

  • but I'm pretty close here.

  • Now, as n grows, what happens to the gap between the upper bound

  • and the lower bound?

  • What does it do?

  • It gets bigger.

  • So my gap gets bigger.

  • That's not so nice.

  • Doesn't always stay 9 forever, but somehow

  • though this is still pretty good, because the gap grows

  • but the gap only grows as square root of n,

  • where the answer-- the bounds-- are growing as n to the 3/2.

  • In other words, my error is somewhere around here,

  • and that gets smaller compared to my answer, which

  • is somewhere around there.

  • And there's a special notation that people use.

  • In fact, let's write that down and then do the notation.

  • Another way of writing this is that the sum i equals 1 to n

  • of square root of i.

  • The leading term here is 2/3 n to the 3/2,

  • and then there's some error term-- delta term here.

  • We'll call that delta n, and we know

  • that the error term is at least 1/3 and, at most,

  • the square root of n minus 2/3.

  • So this delta term is bound by the square root of n.

  • That's getting bigger as n gets big,

  • but this value compared to your answer is getting small.

  • That's nice, and so the way that gets represented is as follows.

  • We would say-- it's using that tilde notation.

  • We write tilde 2/3 times n to the 3/2,

  • and now we've gotten rid of the delta,

  • because this tilde is telling us that everything

  • else out here gets small compared to this as n gets big.

  • And the formal definition-- Let's write out

  • the formal definition for it.

  • Now, a lot of times you'll see people

  • use this symbol to mean about.

  • That's informal.

  • When I'm using it here, it's a very formal meaning

  • mathematically.

  • A function g of x is tilde, a function h of x

  • means that the limit as x goes to infinity of g over h is 1.

  • In other words, that as x goes to infinity--

  • as x gets big-- the ratio of these guys becomes 1.

  • And let's see if that's true here.

  • Well, square root of i equals this,

  • so I need to show the limit of this over that is 1.

  • So let's check that.

  • A limit as n goes to infinity of 2/3 n to the 3/2

  • plus that delta term over 2/3 n to the 3/2.

  • Well, that equals-- divide out by 2/3 n to the 3/2, I get a 1.

  • Did I-- should I have subtracted?

  • No, that's OK.

  • One plus delta n over 2/3 n to the 3/2.

  • If I can pull the 1 out front, that's 1 plus the limit,

  • and this is now delta n is at most square root of n,

  • so I get square root of n over 2/3 n to the 3/2.

  • Square root of n over n to the 3/2, that goes to 0.

  • So this equals 1.

  • So this limit is 1, and so therefore I

  • can say that the sum of the first n square roots

  • is tilde 2/3 n to the 3/2.

  • Any questions about this?

  • We're going to do a lot of this kind of notation next time.

  • Yeah.

  • AUDIENCE: When you took the integral

  • and got 2/3 into the 3/2 minus 1,

  • why did the minus 1 not become part of the actual solution

  • and become part of the delta?

  • PROFESSOR: OK.

  • So you brought it up to here, right?

  • OK.

  • So then I plug that into the integral that

  • appears on both sides here, and here I add the f 1,

  • here I add f n, and now I have the lower bound here

  • and the upper bound here.

  • Are you good with those?

  • All right.

  • Now some judgment takes place, and what I'm really

  • trying to do here is figure out what are the important terms

  • in these bounds as n gets big?

  • How big is this growing as n gets big?

  • Well, as n gets big, the 1/3 is not doing much.

  • As n gets big, the square root of n

  • grows, but it's nothing like what's happening here.

  • If you had to describe to somebody

  • what's going on in this bound, would you start here or here?

  • No.

  • You'd start here.

  • This is the action, and there's a little bit-- the rest is just

  • in the slop, in the air.

  • And so now I've used judgement to say that delta is somewhere

  • in this stuff here.

  • What's really happening, and the nice thing is they match.

  • The lower bound and the upper bound match on that term.

  • So what I do is I write it equals this term

  • plus something that's smaller and, in particular,

  • it's between 1/3 and square root of n minus 2/3.

  • All right.

  • So what I'm trying to capture here

  • is just the guts of what's happening to this function

  • as n grows, and the guts of it is this.

  • It's not exactly equal to 2/3 times n to the 3/2,

  • but it's close and, in fact, if I

  • take the limit of this over that, that limit goes to 1.

  • It's a way of saying they're approximately the same that's

  • called asymptotically the same, and we'll

  • talk a lot more about asymptotic notation next time.

  • We'll give you five more symbols besides tilde that people use.

  • Any questions about-- maybe start with the bounds.

  • Any question on the bounds that we got?

  • That's the integration method, first getting the bounds.

  • You take the integral, you add f of 1 for the lower bound,

  • you add f of n for the upper bound,

  • and it's in between, somewhere in there.

  • Questions there?

  • All right.

  • Then we plugged it in, and now we

  • look at this tilde notation that says-- well, first we'd

  • write it like this.

  • The sum is this value plus an error term and, lo and behold,

  • that error term is small.

  • If I take the limit of the whole thing divided by the big term,

  • I get 1, which means this thing is really not important.

  • So I write this.

  • Questions on that?

  • All right.

  • There's one more case to consider,

  • and now we're going to go back to the integration bounds,

  • and that is when f is a decreasing function,

  • and we're going to do the analysis for that,

  • and then we'll be all done.

  • So we're going to look at integration bounds

  • when f is decreasing and positive still.

  • The example here might be, for example, the sum i

  • equals 1 to n, 1 over the square root of i.

  • Say you had to get some idea of how fast that function is

  • growing as a function of n.

  • I'm summing the first n inverse as the square roots.

  • What is that roughly going to be?

  • How fast does that grow as a function of n?

  • So let's do that.

  • And, of course, 1 over square root of i

  • decreases as i gets bigger.

  • So let's do the general picture again and see what happens.

  • So we have 0, 1, 2, 3, n minus 2, n minus 1, n, and now f of n

  • is the small term and f of n minus 1, f of 3 here, f of 1.

  • Now, I'm going to draw the rectangle.

  • This has area f of 1.

  • This one has area f of 2.

  • This one has area f of 3, and then this one

  • has area f of n minus 1 here, and then, lastly, area f of n.

  • So the sum is the area in the rectangles, just like before,

  • except now the rectangles are getting smaller.

  • Let's draw the integral like we did before.

  • The integral is the area under this curve, f of x here,

  • just like before.

  • So this is f of x, only it's decreasing.

  • Now, let's take the area under this curve, and add f of 1

  • to it.

  • If I take the area under this curve, all the way

  • down to here and then add f of 1, what do I get?

  • Upper bound on my sum.

  • OK.

  • So the sum i equals 1 to n f of i

  • is upper bounded by that guy, which is f of 1,

  • plus my integral, which is the area under the curve.

  • The integral is the area under that curve, starting here,

  • and that contains all these rectangles,

  • and then I just add in f of 1 to get an upper bound.

  • Now, for the lower bound, think about shifting

  • the whole curve left by one.

  • That goes to there, this goes to here,

  • that goes to here, that goes to there, and that goes to there.

  • The area under the curve did not change

  • when I shifted it left by one.

  • This is now my area under the curve.

  • Stops here.

  • What do I get when I take that area and add in this last box,

  • f of n?

  • A lower bound, because it's contained

  • in all the rectangles.

  • Now, what's really weird about these formulas,

  • do they look familiar?

  • Yeah.

  • Yeah.

  • I switched them.

  • Yeah.

  • They're the same formulas we had over here,

  • except we switched the direction on the less than and greater

  • than signs.

  • Well, I swapped f of 1 and f of n, however you

  • want to think about it.

  • The lower bound here in that case

  • became the upper bound in this case.

  • Is that possible that the lower bound became the upper bound?

  • Yeah.

  • Yeah, because what really happened here--

  • which is the big term in this case, fn or f1?

  • f1 is the big term because it's decreasing,

  • so it's totally symmetric.

  • All right?

  • The proof was very similar, so the nice thing

  • is you've only got to remember the bounds are now simple

  • for any sum as long as an increasing or decreasing, it's

  • the same as the integral.

  • The lower bound is the smaller of the first and last term,

  • and the upper bounds are larger of the first and last term.

  • Very easy to remember.

  • Probably don't even need the crib sheet

  • for it, although to be safe, want to write that down.

  • So now it's easy to compute good bounds on the sum

  • of the inverse square roots.

  • Any questions there before I go do it?

  • So let's take the case where we're summing 1

  • over square root of i.

  • So we compute the integral of 1 over square root of x dx.

  • That equals the square root of x over 1/2, evaluated at n and 1.

  • That equals 2 square root of n minus 1,

  • or two square root of n minus 2, and now we can bound the sum.

  • The upper bound is f of 1 plus the integral.

  • The lower bound is f of n plus the integral.

  • What is f of 1?

  • One?

  • One over the square root of 1 is 1.

  • What is f of n?

  • One over the square root of n.

  • Small.

  • So these bounds are pretty close here, right?

  • In fact, this gets really tiny as n gets big,

  • so I'm just going to replace this

  • with 2 square root of n minus 2 and make it a strict lower

  • bound, and this-- cancel there-- I

  • get 2 square root of n minus 1.

  • Wow, these bounds are great.

  • They're within one for all n.

  • That's really good.

  • So we can rewrite this in terms of what really matters.

  • What really matters in these bounds?

  • How fast is this function growing?

  • AUDIENCE: 2 root n.

  • PROFESSOR: 2 root n.

  • That's what really matters, so let's write that down.

  • So this says that the sum i equals 1 to n

  • of 1 over square root i equals 2 square root of n-- we

  • have a minus delta n, where delta is between 1 and 2.

  • And so if I use the tilde notation, what would I

  • write down here for the tilde?

  • Past the tilde?

  • I don't want to mess--

  • AUDIENCE: Tilde.

  • PROFESSOR: --I don't want to keep track of all

  • the delta stuff as n gets big.

  • AUDIENCE: 2 root n.

  • PROFESSOR: 2 root n, because this term

  • over that goes to 0 as n gets large, so let's

  • just check that.

  • So we take the limit as n goes to infinity of 2 root

  • n minus delta n over 2 root n.

  • I'm just checking the definition now.

  • That's what the definition would be.

  • Equals 1 minus the limit as n goes

  • to infinity of 2 over 2 root n.

  • This is 0.

  • So it equals 1.

  • And so now you know that the sum of the first n inverse

  • square roots grows as 2 root n, which is the integral.

  • Yeah.

  • AUDIENCE: [INAUDIBLE] dropped off the lower bound that f of n

  • was 1 over root n?

  • PROFESSOR: Yeah, I dropped it off, because it was so tiny

  • and going to zero, I just made a strict less than.

  • In fact, yes.

  • I don't hurt myself by dropping it off.

  • In fact, the lower bound was a little bit--

  • I made a little weaker lower bound.

  • So this is still true.

  • I just-- it wasn't as tight as it used to be,

  • so I could keep it around.

  • Yeah, it doesn't hurt to keep it around,

  • then it's a less than or equal there.

  • And now this would be something like that.

  • So I could keep it around, but I'm going to get rid of it

  • anyway, because I'm going to go to the tilde notation,

  • and as n gets big, this is really tiny.

  • So in this case, the bounds are great.

  • You can nail it pretty much right on.

  • Yeah.

  • AUDIENCE: You said one over n still there,

  • the number is bigger than it would normally be,

  • so when you take it out, it becomes smaller,

  • so how could you go to a less than [INAUDIBLE]?

  • PROFESSOR: Well, you're saying you don't like

  • the fact I dropped it here?

  • AUDIENCE: Yes.

  • When you drop it, why do you go to a less than instead of

  • [INAUDIBLE]?

  • PROFESSOR: Oh, because I've got a bigger bound that I made less

  • when I dropped it.

  • I took something away, so I know I could never equal this,

  • because I know it's bigger than this.

  • I know that the real answer has to be at least this big,

  • and so it has to be bigger than something smaller.

  • That's why I did it.

  • Any other questions?

  • We'll get more practice tomorrow and next time with this stuff.

PROFESSOR: The following content is provided under a Creative

字幕と単語

ワンタップで英和辞典検索 単語をクリックすると、意味が表示されます

A2 初級

Lec 12|MIT 6.042J コンピュータサイエンスのための数学 2010年秋学期 (Lec 12 | MIT 6.042J Mathematics for Computer Science, Fall 2010)

  • 91 12
    Dou Lin に公開 2021 年 01 月 14 日
動画の中の単語