1
00:00:00,259 --> 00:00:02,800
PROFESSOR: The following content
is provided under a Creative
2
00:00:02,800 --> 00:00:04,340
Commons license.
3
00:00:04,340 --> 00:00:06,660
Your support will help
MIT OpenCourseWare
4
00:00:06,660 --> 00:00:11,020
continue to offer high quality
educational resources for free.
5
00:00:11,020 --> 00:00:13,640
To make a donation or
view additional materials
6
00:00:13,640 --> 00:00:17,365
from hundreds of MIT courses,
visit MIT OpenCourseWare
7
00:00:17,365 --> 00:00:17,990
at ocw.mit.edu.
8
00:00:22,741 --> 00:00:24,740
Today we're going to start
with a simple problem
9
00:00:24,740 --> 00:00:27,670
that many of you may
have already encountered.
10
00:00:27,670 --> 00:00:29,840
For example, when you
got a student loan
11
00:00:29,840 --> 00:00:32,564
or if your family took a
loan out on your house,
12
00:00:32,564 --> 00:00:35,310
you know, a home mortgage
loan, and it's the problem
13
00:00:35,310 --> 00:00:37,420
of pricing an annuity.
14
00:00:37,420 --> 00:00:39,720
An annuity is a
financial instrument
15
00:00:39,720 --> 00:00:42,660
that pays a fixed
amount of money
16
00:00:42,660 --> 00:00:44,910
every year for some
number of years,
17
00:00:44,910 --> 00:00:47,015
and it has a value
associated with it.
18
00:00:47,015 --> 00:00:48,390
For example, with
a student loan,
19
00:00:48,390 --> 00:00:52,540
the value is the amount of
money they gave you to pay MIT,
20
00:00:52,540 --> 00:00:56,180
then later in life-- every
year or every month-- you're
21
00:00:56,180 --> 00:00:57,860
going to send them a check.
22
00:00:57,860 --> 00:01:00,821
And you want to sort of equate
those two things to find out,
23
00:01:00,821 --> 00:01:02,570
are you getting enough
money for the money
24
00:01:02,570 --> 00:01:05,489
you're going to pay back
monthly sometime in the future?
25
00:01:05,489 --> 00:01:09,990
So let's define this, and
there's a lot of variations
26
00:01:09,990 --> 00:01:14,430
on annuities, but we'll
start with one that's called
27
00:01:14,430 --> 00:01:30,450
an n-year $m-dollar
payment annuity,
28
00:01:30,450 --> 00:01:46,950
and it works by paying m dollars
at the start of each year,
29
00:01:46,950 --> 00:01:48,582
and it lasts for n years.
30
00:01:52,770 --> 00:01:55,244
Now, usually n is
finite, but not always,
31
00:01:55,244 --> 00:01:57,160
and in a few minutes
we'll talk about the case
32
00:01:57,160 --> 00:01:59,150
when it's infinite.
33
00:01:59,150 --> 00:02:01,850
But this includes
home mortgages,
34
00:02:01,850 --> 00:02:03,690
where you pay every
month for 30 years.
35
00:02:03,690 --> 00:02:05,800
Megabucks, the lottery.
36
00:02:05,800 --> 00:02:07,890
They don't actually give
you the million dollars.
37
00:02:07,890 --> 00:02:11,030
They give you $50,000
per year for 20 years,
38
00:02:11,030 --> 00:02:13,250
and call it a million bucks.
39
00:02:13,250 --> 00:02:14,880
Retirement plans.
40
00:02:14,880 --> 00:02:17,270
You pay in every
year, and then you
41
00:02:17,270 --> 00:02:19,620
get some big lump sum later.
42
00:02:19,620 --> 00:02:22,880
Life insurance benefits,
you know, and so forth.
43
00:02:22,880 --> 00:02:25,940
Now, if you go to Wall
Street, this is a big deal.
44
00:02:25,940 --> 00:02:28,080
A lot of the stuff that
happens on Wall Street
45
00:02:28,080 --> 00:02:30,580
involves annuities in
one form or another,
46
00:02:30,580 --> 00:02:34,230
packaging them all up
and, in fact, we'll
47
00:02:34,230 --> 00:02:36,120
look at later when
we do probability.
48
00:02:36,120 --> 00:02:38,380
It was how these things
were packaged and sold
49
00:02:38,380 --> 00:02:41,270
that led to the sub-prime
mortgage disaster,
50
00:02:41,270 --> 00:02:44,270
and we'll see how some confusion
over independents, when
51
00:02:44,270 --> 00:02:47,680
you look at random variables,
led to the global recession,
52
00:02:47,680 --> 00:02:48,971
a real disaster.
53
00:02:48,971 --> 00:02:51,220
Of course, some people
understood how all that worked,
54
00:02:51,220 --> 00:02:53,820
made hundreds of billions
of dollars at the same time.
55
00:02:53,820 --> 00:02:57,260
So it was sort of money went
from one place to another.
56
00:02:57,260 --> 00:02:59,790
So it's pretty
important to understand
57
00:02:59,790 --> 00:03:02,930
how much this is worth.
58
00:03:02,930 --> 00:03:05,120
What is this
instrument-- a piece
59
00:03:05,120 --> 00:03:06,620
of paper that says
it will pay you
60
00:03:06,620 --> 00:03:09,160
m dollars at the beginning of
each year for n years, what
61
00:03:09,160 --> 00:03:11,430
is that worth today?
62
00:03:11,430 --> 00:03:14,650
For example, say I
gave you a choice--
63
00:03:14,650 --> 00:03:17,580
the Megabucks choice--
$50,000 a year
64
00:03:17,580 --> 00:03:21,950
for 20 years or a
million dollars today.
65
00:03:21,950 --> 00:03:26,430
How many people would prefer
the $50,000 a year for 20 years?
66
00:03:26,430 --> 00:03:27,030
A few of you.
67
00:03:27,030 --> 00:03:30,840
How many would prefer the
million bucks right up front?
68
00:03:30,840 --> 00:03:31,670
Much better.
69
00:03:31,670 --> 00:03:32,630
OK.
70
00:03:32,630 --> 00:03:34,970
Always better to have
the cash in hand,
71
00:03:34,970 --> 00:03:36,900
because there's things
like inflation--
72
00:03:36,900 --> 00:03:39,680
pretty low now-- interest.
73
00:03:39,680 --> 00:03:41,160
You can put the
money in the bank
74
00:03:41,160 --> 00:03:44,980
or invest it and make
some money hopefully.
75
00:03:44,980 --> 00:03:47,170
So the million dollars
today is a lot better,
76
00:03:47,170 --> 00:03:50,960
which is why the State pays you
50 grand a year for 20 years.
77
00:03:50,960 --> 00:03:53,614
It's better for them, and
they call it a million bucks.
78
00:03:53,614 --> 00:03:55,030
So that was pretty
clear, but what
79
00:03:55,030 --> 00:04:01,950
if I gave you this option-- 700
grand today or 50 grand a year
80
00:04:01,950 --> 00:04:03,700
for 20 years?
81
00:04:03,700 --> 00:04:08,090
How many people want the cash
upfront-- 700 grand only.
82
00:04:08,090 --> 00:04:08,660
A few.
83
00:04:08,660 --> 00:04:13,310
How many people want 50
grand a year for 20 years?
84
00:04:13,310 --> 00:04:15,770
All right, we're almost--
that's pretty close to half way.
85
00:04:15,770 --> 00:04:20,750
How about 500 grand today versus
50 grand a year for 20 years?
86
00:04:20,750 --> 00:04:24,511
How many want half
a million today?
87
00:04:24,511 --> 00:04:25,760
A lot of people like the cash.
88
00:04:25,760 --> 00:04:28,218
You know, it's this kind of a
time, you have the recession,
89
00:04:28,218 --> 00:04:29,617
it's a disaster on Wall Street.
90
00:04:29,617 --> 00:04:31,700
You know, Street Wall
Street didn't like the cash.
91
00:04:31,700 --> 00:04:34,100
How many want, instead
of a half a million
92
00:04:34,100 --> 00:04:37,252
up front, 50 grand
a year for 20 years?
93
00:04:37,252 --> 00:04:38,710
All right, now
we're about halfway.
94
00:04:38,710 --> 00:04:39,850
All right, well
that's pretty good.
95
00:04:39,850 --> 00:04:41,815
So we're going to find
out what you should pay,
96
00:04:41,815 --> 00:04:44,750
or at least one way
of estimating that.
97
00:04:44,750 --> 00:04:48,460
Now, to do that, we've
got to figure out what
98
00:04:48,460 --> 00:04:53,670
$1 today is worth in a year.
99
00:04:53,670 --> 00:05:00,364
And to do that, we
make an assumption,
100
00:05:00,364 --> 00:05:01,780
and the assumption
is that there's
101
00:05:01,780 --> 00:05:06,600
a fixed-- we'll call
it an interest rate.
102
00:05:06,600 --> 00:05:09,610
It's sort of the devaluation
of the money per year.
103
00:05:12,180 --> 00:05:13,490
And we're going to call it p.
104
00:05:13,490 --> 00:05:15,000
Later we'll plug
in values for p,
105
00:05:15,000 --> 00:05:18,672
but you can think of
it as like 6%, 1%.
106
00:05:18,672 --> 00:05:20,880
You know, it's the money,
if you put money in a bank,
107
00:05:20,880 --> 00:05:23,650
they'll give you some
percent back every year.
108
00:05:23,650 --> 00:05:25,639
And, of course, the fact
that different people
109
00:05:25,639 --> 00:05:27,430
have different ideas
of what this would be,
110
00:05:27,430 --> 00:05:29,950
allows people to make
money on Wall Street.
111
00:05:29,950 --> 00:05:32,440
As we'll see, a
slight difference in p
112
00:05:32,440 --> 00:05:36,460
can make big differences in
what the annuity is worth.
113
00:05:36,460 --> 00:05:48,380
So for example, $1 today
is going to equal 1 plus p
114
00:05:48,380 --> 00:05:50,662
dollars in one year.
115
00:05:54,360 --> 00:05:57,290
Similarly, $1 today--
how much is that
116
00:05:57,290 --> 00:05:59,645
going to be worth in two years?
117
00:06:03,910 --> 00:06:06,528
Say that p stays fixed,
the same over all time.
118
00:06:10,060 --> 00:06:14,360
One plus p squared,
because every year you
119
00:06:14,360 --> 00:06:16,970
multiply what you got by
1 plus p, because that's
120
00:06:16,970 --> 00:06:18,560
the interest you're getting.
121
00:06:18,560 --> 00:06:20,940
All right, we'll think of
it in terms of interest.
122
00:06:20,940 --> 00:06:28,070
In three years, $1 today
is worth 1 plus p cubed in
123
00:06:28,070 --> 00:06:32,660
three years and so forth.
124
00:06:32,660 --> 00:06:33,160
All right.
125
00:06:33,160 --> 00:06:36,750
Now, what we really care about
is what's $1, or m dollars,
126
00:06:36,750 --> 00:06:40,090
worth today if you're
getting it next year?
127
00:06:40,090 --> 00:06:44,026
So we need to sort of flip
this back the other way.
128
00:06:47,930 --> 00:06:56,510
So what is $1 in a year
worth today in terms of p?
129
00:06:59,160 --> 00:07:01,722
So if I'm going to
be paid $1 in a year,
130
00:07:01,722 --> 00:07:03,930
what would be the equivalent
amount to be paid today?
131
00:07:07,580 --> 00:07:13,480
One over 1 plus p, because
what's happening here
132
00:07:13,480 --> 00:07:17,690
is, as you go forward in a year,
you just multiply by 1 plus p.
133
00:07:17,690 --> 00:07:24,510
So 1 over 1 plus p turns
into $1 in a year-- being
134
00:07:24,510 --> 00:07:27,270
paid in a year.
135
00:07:27,270 --> 00:07:28,130
All right.
136
00:07:28,130 --> 00:07:35,027
What is $1 a year in
two years worth today?
137
00:07:37,650 --> 00:07:42,610
One over 1 plus p squared.
138
00:07:42,610 --> 00:07:48,060
So $1 in two years is
worth this much today.
139
00:07:48,060 --> 00:07:50,800
Well, now we can use
this to go figure
140
00:07:50,800 --> 00:07:55,080
out the current value
of that annuity.
141
00:07:55,080 --> 00:07:59,060
We just figure out what every
payment is worth today and then
142
00:07:59,060 --> 00:08:01,380
add it up.
143
00:08:01,380 --> 00:08:04,220
So we'll put the
payments over here,
144
00:08:04,220 --> 00:08:06,890
and we'll compute
the current value
145
00:08:06,890 --> 00:08:08,500
of every payment on this side.
146
00:08:11,840 --> 00:08:13,580
So with the annuity,
the way we've
147
00:08:13,580 --> 00:08:16,630
set it up is it pays n dollars
at the start of every year,
148
00:08:16,630 --> 00:08:19,970
so the first payment is now.
149
00:08:19,970 --> 00:08:23,710
So the first of the
n payments is now,
150
00:08:23,710 --> 00:08:27,130
and since it's being paid
now, that's worth m dollars.
151
00:08:27,130 --> 00:08:30,320
There's no devaluation.
152
00:08:30,320 --> 00:08:36,789
The next payment is m
dollars in one year,
153
00:08:36,789 --> 00:08:43,360
and so that's going to be
worth m over 1 plus p today.
154
00:08:43,360 --> 00:08:48,850
And the next payment is
m dollars in two years.
155
00:08:48,850 --> 00:08:53,870
That's worth m over
1 plus p squared,
156
00:08:53,870 --> 00:08:57,880
and we keep on going
until the last payment.
157
00:08:57,880 --> 00:09:03,647
It's the n-th payment, so it's
m dollars in n minus 1 years.
158
00:09:06,330 --> 00:09:13,260
And so that's going to
be worth m over 1 plus p
159
00:09:13,260 --> 00:09:14,437
to the n minus 1.
160
00:09:16,891 --> 00:09:17,390
All right.
161
00:09:17,390 --> 00:09:20,440
So we can compute the current
value of all those payments,
162
00:09:20,440 --> 00:09:24,430
then the annuity is computed--
the value is computed just
163
00:09:24,430 --> 00:09:28,820
by adding these up, of
all the current values.
164
00:09:28,820 --> 00:09:39,012
So the total current value is
the sum i equals 0 to n minus 1
165
00:09:39,012 --> 00:09:44,490
of m over 1 plus p to the i.
166
00:09:44,490 --> 00:09:46,273
And that is the
total current value.
167
00:09:50,300 --> 00:09:56,830
That's what you should
pay today for the annuity.
168
00:09:56,830 --> 00:09:59,590
Any questions?
169
00:09:59,590 --> 00:10:02,150
What we did here?
170
00:10:02,150 --> 00:10:03,890
All right.
171
00:10:03,890 --> 00:10:07,370
Well, of course, what we'd like
is a closed form expression
172
00:10:07,370 --> 00:10:08,427
here.
173
00:10:08,427 --> 00:10:10,260
Something that's simple
so we could actually
174
00:10:10,260 --> 00:10:14,980
get a feel without having
to add up all those terms,
175
00:10:14,980 --> 00:10:16,520
and that's not hard to get.
176
00:10:16,520 --> 00:10:20,560
In fact, let's put
this sum in a form
177
00:10:20,560 --> 00:10:23,420
that might be more familiar.
178
00:10:23,420 --> 00:10:27,310
This equals-- we'll pull
the m out in front--
179
00:10:27,310 --> 00:10:30,370
and let's use x to be 1
over 1 plus p to the i.
180
00:10:37,140 --> 00:10:47,330
And so x equals 1 over 1 plus
p, and I wrote it this way
181
00:10:47,330 --> 00:10:51,249
because this might be familiar.
182
00:10:51,249 --> 00:10:53,040
Does everybody remember
that from-- I think
183
00:10:53,040 --> 00:10:55,112
it was the second recitation?
184
00:10:57,862 --> 00:10:59,070
Anybody remember the formula?
185
00:10:59,070 --> 00:11:00,180
What this evaluates to?
186
00:11:02,980 --> 00:11:09,380
The sum of x to the i, where
i goes from 0 to n minus 1?
187
00:11:09,380 --> 00:11:11,170
Remember that?
188
00:11:11,170 --> 00:11:12,970
One minus x to the n.
189
00:11:15,730 --> 00:11:18,820
Remember 1 minus x.
190
00:11:18,820 --> 00:11:20,550
In the second
recitation, I think,
191
00:11:20,550 --> 00:11:23,550
we proved that this equals that.
192
00:11:23,550 --> 00:11:26,370
What was the proof
technique we used?
193
00:11:26,370 --> 00:11:27,391
Induction.
194
00:11:27,391 --> 00:11:27,890
OK?
195
00:11:33,490 --> 00:11:37,476
So, in fact, there's
a theorem here.
196
00:11:41,060 --> 00:11:46,730
For all n bigger and equal
to 1 and x not equal to 1,
197
00:11:46,730 --> 00:11:52,360
we proved the sum from i equals
0 to n minus 1 x to the i
198
00:11:52,360 --> 00:11:57,270
equals 1 minus x to
the n over 1 minus x.
199
00:11:57,270 --> 00:11:58,870
And so this is a
nice, closed form.
200
00:11:58,870 --> 00:12:04,040
No sum any more, just
that, which is nice.
201
00:12:04,040 --> 00:12:07,960
Now, induction proved
it was the right answer.
202
00:12:07,960 --> 00:12:13,450
Once you knew it-- we gave
it to you-- using induction
203
00:12:13,450 --> 00:12:16,100
to prove that
theorem wasn't hard.
204
00:12:16,100 --> 00:12:19,310
What we're going to look at
doing this week and next week
205
00:12:19,310 --> 00:12:21,580
is figuring out how
to figure out this
206
00:12:21,580 --> 00:12:23,550
was the answer in
the first place.
207
00:12:23,550 --> 00:12:28,240
Methods for doing that-- to
evaluate the sum-- and there's
208
00:12:28,240 --> 00:12:32,050
a lot of ways that you can
do that particular sum.
209
00:12:32,050 --> 00:12:36,480
Probably the easiest is known
as the perturbation method.
210
00:12:40,050 --> 00:12:42,090
This sometimes works.
211
00:12:42,090 --> 00:12:45,200
Certainly with sums like
that, it often works.
212
00:12:45,200 --> 00:12:46,460
The idea is as follows.
213
00:12:46,460 --> 00:12:49,460
We're trying to compute
the sum S, which is 1
214
00:12:49,460 --> 00:12:57,500
plus x plus x squared
plus x to the n minus 1,
215
00:12:57,500 --> 00:13:01,230
and what we're going to do
is perturb it a little bit
216
00:13:01,230 --> 00:13:05,210
and then subtract to
get big cancellation.
217
00:13:05,210 --> 00:13:06,620
In this case, it's
pretty simple.
218
00:13:06,620 --> 00:13:19,130
We multiply the sum by x to get
x plus x squared plus-- I've
219
00:13:19,130 --> 00:13:22,380
defined S to be that,
x times S-- well, I
220
00:13:22,380 --> 00:13:28,450
get x plus x squared and
so forth, up to x to the n,
221
00:13:28,450 --> 00:13:32,673
and now I can subtract one from
the other and almost everything
222
00:13:32,673 --> 00:13:33,173
cancels.
223
00:13:36,020 --> 00:13:42,220
So I get 1 minus x
times S equals 1.
224
00:13:42,220 --> 00:13:45,450
These cancel, cancel, cancel.
225
00:13:45,450 --> 00:13:48,750
Minus x to the n.
226
00:13:48,750 --> 00:13:54,310
And therefore S equals 1 minus
x to the n over 1 minus x.
227
00:13:57,000 --> 00:14:01,820
So that's a vague method.
228
00:14:01,820 --> 00:14:04,930
This gets used all the time
in applied mathematics,
229
00:14:04,930 --> 00:14:06,930
and they call it the
perturbation method.
230
00:14:06,930 --> 00:14:10,150
Take your sum, wiggle
it around a little bit,
231
00:14:10,150 --> 00:14:11,990
get something that looks
close, subtract it,
232
00:14:11,990 --> 00:14:14,201
everything cancels,
life is nice,
233
00:14:14,201 --> 00:14:16,284
and all of a sudden you've
figured out the answer.
234
00:14:21,530 --> 00:14:26,930
So getting back to
our annuity problem,
235
00:14:26,930 --> 00:14:31,660
we can plug that
formula back in here.
236
00:14:31,660 --> 00:14:39,030
So the value of the annuity
is m times 1 minus x to the n
237
00:14:39,030 --> 00:14:41,080
over 1 minus x.
238
00:14:41,080 --> 00:14:47,570
We'll plug in x equals
1 over 1 plus p,
239
00:14:47,570 --> 00:14:54,670
and we get m 1 minus
1 over 1 plus p
240
00:14:54,670 --> 00:15:01,830
to the n over 1 minus 1 over
1 plus p, just plugging in.
241
00:15:01,830 --> 00:15:05,150
And now to simplify this, I'll
multiply the top and bottom
242
00:15:05,150 --> 00:15:11,920
by 1 plus p, and I'll get 1
plus p minus 1 on the bottom.
243
00:15:11,920 --> 00:15:14,080
Just gives me a p on the bottom.
244
00:15:14,080 --> 00:15:19,040
I have a 1 plus p on
the top minus 1 over 1
245
00:15:19,040 --> 00:15:23,680
plus p to the n
minus 1, all over p.
246
00:15:27,740 --> 00:15:30,850
So now we have a formula--
closed form expression
247
00:15:30,850 --> 00:15:33,840
formula-- for the
value of the annuity.
248
00:15:33,840 --> 00:15:37,400
All's we've got to plug in
is m, the payment every year,
249
00:15:37,400 --> 00:15:41,560
n, the number of years, and
then p, the interest rate.
250
00:15:41,560 --> 00:15:51,540
And so, for example, if
we made m be $50,000,
251
00:15:51,540 --> 00:15:52,390
as in the lottery.
252
00:15:52,390 --> 00:15:58,640
We made n be 20 years, and
say we took 6% interest, which
253
00:15:58,640 --> 00:16:03,710
is actually very good these
days, and I plug those in here,
254
00:16:03,710 --> 00:16:12,710
the value is going
to be $607,906.
255
00:16:12,710 --> 00:16:13,210
All right.
256
00:16:13,210 --> 00:16:17,680
So those of you that preferred
700 grand-- if you assume 6%
257
00:16:17,680 --> 00:16:19,560
interest-- you're right.
258
00:16:19,560 --> 00:16:21,920
Those of you who
preferred 500 grand, no,
259
00:16:21,920 --> 00:16:25,360
you're better off waiting and
getting your 50 grand a year.
260
00:16:25,360 --> 00:16:28,500
Now, of course, if the
interest rate is lower,
261
00:16:28,500 --> 00:16:31,020
well, that changes things.
262
00:16:31,020 --> 00:16:32,800
That shifts it even more.
263
00:16:32,800 --> 00:16:36,360
The annuity is worth even more
if the interest rate is lower--
264
00:16:36,360 --> 00:16:38,540
if p is smaller.
265
00:16:38,540 --> 00:16:42,400
In fact, say p was 0.
266
00:16:42,400 --> 00:16:45,310
Say the interest rate is 0, so
$1 today equals $1 tomorrow,
267
00:16:45,310 --> 00:16:48,350
then what is the lottery worth?
268
00:16:48,350 --> 00:16:50,130
A million dollars.
269
00:16:50,130 --> 00:16:53,230
And the bigger p gets, the
less your payment is worth.
270
00:16:57,660 --> 00:16:58,915
Any questions about that?
271
00:17:01,530 --> 00:17:03,320
OK.
272
00:17:03,320 --> 00:17:11,170
What if you were paid $50,000 a
year forever-- you live forever
273
00:17:11,170 --> 00:17:13,950
or it goes to your
estate and your heirs,
274
00:17:13,950 --> 00:17:18,960
$50,000 a year forever or
a million dollars today.
275
00:17:21,609 --> 00:17:25,200
How many people want the
million dollars today?
276
00:17:25,200 --> 00:17:29,530
How many want 50
grand a year forever?
277
00:17:29,530 --> 00:17:30,730
Sounds good.
278
00:17:30,730 --> 00:17:34,560
You know, that's an infinite
amount of money, sort of.
279
00:17:34,560 --> 00:17:36,190
It's not as good as it sounds.
280
00:17:36,190 --> 00:17:39,290
Let's see why.
281
00:17:39,290 --> 00:17:45,150
So this is a case where
n equals infinity,
282
00:17:45,150 --> 00:17:50,840
and so I'll claim that
if n equals infinity,
283
00:17:50,840 --> 00:17:56,100
then the value of this
annuity is just m times 1
284
00:17:56,100 --> 00:17:57,180
plus p over p.
285
00:18:00,100 --> 00:18:02,789
Let's see why that's the case.
286
00:18:02,789 --> 00:18:04,330
You know, it sounds
hard to evaluate,
287
00:18:04,330 --> 00:18:07,930
because it's an infinite
number of payments,
288
00:18:07,930 --> 00:18:12,250
but what happens here
when n goes to infinity?
289
00:18:12,250 --> 00:18:15,300
What happens to this thing?
290
00:18:15,300 --> 00:18:18,530
That goes to 0 as
n goes to infinity,
291
00:18:18,530 --> 00:18:20,000
as long as p is bigger than 0.
292
00:18:20,000 --> 00:18:22,800
So we're going to
assume 6% interest.
293
00:18:22,800 --> 00:18:25,340
So that goes away, so
the annuity is worth just
294
00:18:25,340 --> 00:18:31,000
that, m times 1 plus p over
p, because the limit as n
295
00:18:31,000 --> 00:18:36,550
goes to infinity of 1 over
1 plus p to the n minus 1,
296
00:18:36,550 --> 00:18:39,890
that's going to 0.
297
00:18:39,890 --> 00:19:02,390
So the value for m is $50,000,
and at 6% V is only $883,000.
298
00:19:02,390 --> 00:19:04,450
So you're better off
taking a million dollars
299
00:19:04,450 --> 00:19:08,704
today than $50,000
a year forever.
300
00:19:08,704 --> 00:19:10,620
Now, if you think about
it, and think about it
301
00:19:10,620 --> 00:19:12,350
as an interest
rate, why should it
302
00:19:12,350 --> 00:19:14,950
be obvious that you're better
off with a million dollars
303
00:19:14,950 --> 00:19:19,179
today than 50 grand
a year forever?
304
00:19:19,179 --> 00:19:21,470
Think about what you could
do with that million dollars
305
00:19:21,470 --> 00:19:27,790
if you had it today
at 6% interest.
306
00:19:27,790 --> 00:19:31,710
What would you do with it to
make more money than 50 grand
307
00:19:31,710 --> 00:19:32,360
a year forever?
308
00:19:32,360 --> 00:19:33,478
Yeah.
309
00:19:33,478 --> 00:19:36,102
AUDIENCE: You could have like--
you could make $50,000 per year
310
00:19:36,102 --> 00:19:37,754
just off of [INAUDIBLE].
311
00:19:37,754 --> 00:19:38,420
PROFESSOR: Yeah.
312
00:19:38,420 --> 00:19:40,820
In this model, if the
interest rate is 6%,
313
00:19:40,820 --> 00:19:41,820
you can put in the bank.
314
00:19:41,820 --> 00:19:45,300
It makes 6% every year, that's
60 grand a year forever.
315
00:19:45,300 --> 00:19:48,150
Better than 50 grand
a year forever.
316
00:19:48,150 --> 00:19:50,294
So maybe it's-- even
without doing the math,
317
00:19:50,294 --> 00:19:51,960
you can tell which
way it's going to go,
318
00:19:51,960 --> 00:19:54,396
but this tells you
exactly what it's worth.
319
00:19:58,460 --> 00:19:59,102
Any questions?
320
00:20:02,340 --> 00:20:04,362
OK.
321
00:20:04,362 --> 00:20:04,862
Yeah.
322
00:20:04,862 --> 00:20:06,428
AUDIENCE: [INAUDIBLE]
current value--
323
00:20:06,428 --> 00:20:08,554
that's how much it's
worth to you right now.
324
00:20:08,554 --> 00:20:09,220
PROFESSOR: Yeah.
325
00:20:09,220 --> 00:20:14,010
AUDIENCE: So and, like, if
you have $1 in the future--
326
00:20:14,010 --> 00:20:15,086
PROFESSOR: Yeah.
327
00:20:15,086 --> 00:20:17,869
AUDIENCE: --where S right
now is m over 1 plus p--
328
00:20:17,869 --> 00:20:18,535
PROFESSOR: Yeah.
329
00:20:18,535 --> 00:20:21,118
AUDIENCE: --is it worth less to
you [INAUDIBLE] then later on,
330
00:20:21,118 --> 00:20:23,000
it's going to be
worth more to you.
331
00:20:23,000 --> 00:20:24,930
PROFESSOR: Ah, so
if you move yourself
332
00:20:24,930 --> 00:20:28,584
forward in time, $1 a year, in
a year it'll worth $1 to you--
333
00:20:28,584 --> 00:20:29,360
AUDIENCE: Yeah.
334
00:20:29,360 --> 00:20:32,490
PROFESSOR: --but today it's
worth less than $1 to you,
335
00:20:32,490 --> 00:20:35,070
because you could take the
dollar today and invest
336
00:20:35,070 --> 00:20:38,180
in the bank, and it's worth more
in a year, because the money
337
00:20:38,180 --> 00:20:41,700
grows in value, as a
way to think of it,
338
00:20:41,700 --> 00:20:43,510
because you can
earn interest on it.
339
00:20:43,510 --> 00:20:44,104
What's that?
340
00:20:44,104 --> 00:20:45,760
AUDIENCE: You could spend it.
341
00:20:45,760 --> 00:20:46,480
PROFESSOR: Yeah.
342
00:20:46,480 --> 00:20:48,030
Yeah, if you just
spend it, well,
343
00:20:48,030 --> 00:20:49,571
then at least you
had the use of what
344
00:20:49,571 --> 00:20:51,009
you spent it on for the year.
345
00:20:51,009 --> 00:20:52,800
So there's some other
kind of value, right?
346
00:20:52,800 --> 00:20:55,660
Maybe you bought a
house or something
347
00:20:55,660 --> 00:20:59,410
that-- maybe something that
even appreciated in value.
348
00:20:59,410 --> 00:21:00,610
OK.
349
00:21:00,610 --> 00:21:04,396
But these things
get sort of squishy,
350
00:21:04,396 --> 00:21:05,770
and that is where
a lot of people
351
00:21:05,770 --> 00:21:08,890
make money on Wall Street, is
because different companies
352
00:21:08,890 --> 00:21:10,330
have different needs for money.
353
00:21:10,330 --> 00:21:11,860
They have different views of
what the interest rates are
354
00:21:11,860 --> 00:21:14,180
going to be, and you
can play in the middle
355
00:21:14,180 --> 00:21:16,170
and make a lot of
money that way.
356
00:21:35,220 --> 00:21:39,620
So more generally, there's
a corollary to the theorem,
357
00:21:39,620 --> 00:21:44,030
and that is that if the absolute
value of x is less than 1,
358
00:21:44,030 --> 00:21:51,650
then the sum i equals 0
to infinity x to the i
359
00:21:51,650 --> 00:21:56,080
is just 1 over 1 minus x.
360
00:21:56,080 --> 00:21:59,350
We didn't prove this back
in the second recitation,
361
00:21:59,350 --> 00:22:02,130
because there's no
n to induct on here,
362
00:22:02,130 --> 00:22:05,220
but the proof is simple
from the theorem.
363
00:22:05,220 --> 00:22:08,060
And it's simply because
if x is less than 1,
364
00:22:08,060 --> 00:22:13,330
an absolute value, as n goes
to infinity, that goes to 0,
365
00:22:13,330 --> 00:22:15,410
and so you're just left
with 1 over 1 minus x.
366
00:22:26,650 --> 00:22:31,680
So, for example,
what's this sum?
367
00:22:31,680 --> 00:22:33,075
This one you all know, I'm sure.
368
00:22:37,010 --> 00:22:37,880
Out to infinity.
369
00:22:37,880 --> 00:22:40,970
What's that sum to?
370
00:22:40,970 --> 00:22:41,600
To 2.
371
00:22:41,600 --> 00:22:42,250
Yeah.
372
00:22:42,250 --> 00:22:47,710
It's 1 over 1 minus
1/2, which is 2.
373
00:22:47,710 --> 00:22:55,370
What about this sum
out to infinity?
374
00:22:55,370 --> 00:22:56,505
What does that sum to?
375
00:22:59,263 --> 00:23:01,430
AUDIENCE: [INAUDIBLE]
376
00:23:01,430 --> 00:23:07,700
PROFESSOR: Yeah, 3/2, 1
over 1 minus 1/3 is 3/2.
377
00:23:07,700 --> 00:23:09,920
So, easy corollaries.
378
00:23:09,920 --> 00:23:12,460
These are all examples
of geometric series.
379
00:23:12,460 --> 00:23:14,600
That's what a definition
of a geometric series is.
380
00:23:14,600 --> 00:23:16,810
Something that's going
down by a fixed-- each term
381
00:23:16,810 --> 00:23:19,490
goes down by the same
fixed amount every time.
382
00:23:19,490 --> 00:23:22,580
And geometric
series, generally sum
383
00:23:22,580 --> 00:23:26,140
to something that is very
close to the largest term.
384
00:23:26,140 --> 00:23:28,590
In this case, it's 1.
385
00:23:28,590 --> 00:23:31,380
Very common, because
of that formula.
386
00:23:31,380 --> 00:23:32,772
It's 1 over 1 minus x.
387
00:23:40,270 --> 00:23:43,720
Any questions about this
or geometric series?
388
00:23:46,760 --> 00:23:48,280
All right.
389
00:23:48,280 --> 00:23:51,140
Well, those are
straight geometric sums.
390
00:23:51,140 --> 00:23:53,500
Sometimes you run into things
that are a little bit more
391
00:23:53,500 --> 00:23:54,930
complicated.
392
00:23:54,930 --> 00:24:01,570
For example, say I have this
kind of a sum, i equals 1 to n,
393
00:24:01,570 --> 00:24:05,030
i times x to the i.
394
00:24:05,030 --> 00:24:11,100
Now, those are adding up x
plus 2x squared plus 3x cubed,
395
00:24:11,100 --> 00:24:16,369
and so forth, up
to n x to the n.
396
00:24:16,369 --> 00:24:18,160
You know, that's a
little more complicated.
397
00:24:18,160 --> 00:24:21,480
The terms are
getting-- decreasing
398
00:24:21,480 --> 00:24:24,680
by a factor of x, increasing by
1 in terms of the coefficient
399
00:24:24,680 --> 00:24:25,420
every time.
400
00:24:25,420 --> 00:24:27,200
A little trickier.
401
00:24:27,200 --> 00:24:31,280
So say we wanted to get a
closed form expression for that?
402
00:24:31,280 --> 00:24:33,130
There are several
ways we can do it.
403
00:24:33,130 --> 00:24:37,190
The first would be to try to use
perturbation-- the perturbation
404
00:24:37,190 --> 00:24:37,900
method.
405
00:24:37,900 --> 00:24:40,730
Let's try that.
406
00:24:40,730 --> 00:24:48,370
So we write S equals x plus 2x
squared plus 3x cubed plus nx
407
00:24:48,370 --> 00:24:51,920
to the n, and let's try
the same perturbation.
408
00:24:51,920 --> 00:24:57,610
Multiply by x, I
get that x squared
409
00:24:57,610 --> 00:25:09,420
plus 2x cubed plus n minus 1x to
the n, plus nx to the n plus 1.
410
00:25:09,420 --> 00:25:12,370
And then I subtract to try
to get all the cancellation.
411
00:25:15,220 --> 00:25:17,410
So then I do that.
412
00:25:17,410 --> 00:25:24,540
I get 1 minus x times S. Well, I
didn't quite cancel everything.
413
00:25:24,540 --> 00:25:31,960
X plus x squared
plus x cubed plus x
414
00:25:31,960 --> 00:25:37,960
to the n plus n-- or
minus nx to the n plus 1.
415
00:25:37,960 --> 00:25:41,010
Ah, it didn't quite work.
416
00:25:41,010 --> 00:25:43,708
Anybody see a way that
I can fix this up?
417
00:25:49,480 --> 00:25:51,610
What about this piece?
418
00:25:51,610 --> 00:25:53,020
That's still a mess here.
419
00:25:53,020 --> 00:25:56,240
Can I simplify that?
420
00:25:56,240 --> 00:25:57,522
Yeah?
421
00:25:57,522 --> 00:25:58,474
AUDIENCE: [INAUDIBLE]
422
00:26:05,150 --> 00:26:06,761
PROFESSOR: Yeah.
423
00:26:06,761 --> 00:26:07,260
There's
424
00:26:07,260 --> 00:26:08,990
a simpler way.
425
00:26:08,990 --> 00:26:09,721
Yeah.
426
00:26:09,721 --> 00:26:11,220
AUDIENCE: That's a
geometric series.
427
00:26:11,220 --> 00:26:13,160
PROFESSOR: That's
a geometric series.
428
00:26:13,160 --> 00:26:16,360
We just got the formula
for it, so that's easy.
429
00:26:16,360 --> 00:26:25,140
This equals 1 minus x to the
n over 1 minus x minus the 1,
430
00:26:25,140 --> 00:26:26,910
because I'm missing the 1 here.
431
00:26:26,910 --> 00:26:29,040
So we can rewrite this
whole thing over here.
432
00:26:39,551 --> 00:26:40,050
Oops.
433
00:26:40,050 --> 00:26:40,550
Yikes.
434
00:26:40,550 --> 00:26:41,481
Got attacked.
435
00:26:49,880 --> 00:26:50,560
What's that?
436
00:26:50,560 --> 00:26:53,960
AUDIENCE: Would it be 1
minus x should be n plus 1?
437
00:26:53,960 --> 00:26:56,710
PROFESSOR: Yes it would.
438
00:26:56,710 --> 00:26:57,360
That's right.
439
00:26:57,360 --> 00:26:59,630
I've got to add 1 to there.
440
00:26:59,630 --> 00:27:00,200
OK.
441
00:27:00,200 --> 00:27:02,630
So that's good.
442
00:27:02,630 --> 00:27:08,040
So that says that
1 minus x times S
443
00:27:08,040 --> 00:27:15,317
equals 1 minus x to the n
plus 1 over 1 minus x minus 1,
444
00:27:15,317 --> 00:27:17,650
and then I've got to remember
to subtract that term too.
445
00:27:17,650 --> 00:27:21,630
Minus nx to the n plus 1.
446
00:27:21,630 --> 00:27:24,700
That means now I
just divide through,
447
00:27:24,700 --> 00:27:27,990
and I simplify-- divide through
by 1 minus x-- and simplify,
448
00:27:27,990 --> 00:27:30,070
and I get the following formula.
449
00:27:30,070 --> 00:27:32,390
I won't go through all the
details, but it's not hard.
450
00:27:45,460 --> 00:27:48,590
Let's see if I got that right.
451
00:27:48,590 --> 00:27:50,450
Yeah, that looks right.
452
00:27:50,450 --> 00:27:52,780
OK, so that is the
closed form expression
453
00:27:52,780 --> 00:27:55,839
for that sum, which we can
get from the perturbation
454
00:27:55,839 --> 00:27:57,380
method and the fact
that we'd already
455
00:27:57,380 --> 00:28:00,940
done the geometric series.
456
00:28:00,940 --> 00:28:05,700
There's another way to
compute these kinds of sums,
457
00:28:05,700 --> 00:28:08,267
which I want to show you,
because it can be useful.
458
00:28:16,170 --> 00:28:19,180
So we're going to do the same
sum and derive the formula
459
00:28:19,180 --> 00:28:21,180
a different way.
460
00:28:21,180 --> 00:28:31,720
This method is called
the derivative method,
461
00:28:31,720 --> 00:28:34,440
and the idea is to start
with a geometric series which
462
00:28:34,440 --> 00:28:39,280
it's close to and then
take a derivative.
463
00:28:39,280 --> 00:28:43,700
So for x not equal to 1, we
already know from the theorem
464
00:28:43,700 --> 00:28:50,080
that i equals 0 to n, x to the
i equals 1 minus x to the n
465
00:28:50,080 --> 00:28:53,170
plus 1 over 1 minus x.
466
00:28:53,170 --> 00:28:54,120
That was the theorem.
467
00:28:54,120 --> 00:28:57,010
We already know that.
468
00:28:57,010 --> 00:28:59,670
Now, I can take the
derivative of both sides,
469
00:28:59,670 --> 00:29:03,220
and let's see what we get
by taking the derivative.
470
00:29:03,220 --> 00:29:07,440
Well, here I get the sum.
471
00:29:07,440 --> 00:29:10,320
The derivative of x to the
i is just i times x to the i
472
00:29:10,320 --> 00:29:13,020
minus 1.
473
00:29:13,020 --> 00:29:16,310
The derivative over here
is a little messier.
474
00:29:16,310 --> 00:29:19,400
I've got to have--
well, I take 1 minus x
475
00:29:19,400 --> 00:29:20,570
times a derivative of that.
476
00:29:23,530 --> 00:29:33,020
Derivative of this is now
minus n plus 1, x to the n.
477
00:29:33,020 --> 00:29:36,980
Then I take this times
the derivative of that
478
00:29:36,980 --> 00:29:44,790
is now minus minus 1, 1
minus x to the n plus 1,
479
00:29:44,790 --> 00:29:48,120
and then I divide
by that squared.
480
00:29:52,730 --> 00:29:58,390
Now, when we compute all that
out, we get this, 1 minus n
481
00:29:58,390 --> 00:30:06,690
plus 1, x to the n plus
nx to the n plus 1 over 1
482
00:30:06,690 --> 00:30:09,689
minus x squared.
483
00:30:09,689 --> 00:30:11,230
I won't drag you
through the algebra,
484
00:30:11,230 --> 00:30:13,480
but it's not hard to
go from there to there.
485
00:30:13,480 --> 00:30:17,020
This is pretty close
to what we wanted.
486
00:30:17,020 --> 00:30:25,540
We're trying to figure out
this, and we almost got there.
487
00:30:25,540 --> 00:30:28,470
What do I do to finish it up?
488
00:30:28,470 --> 00:30:29,470
AUDIENCE: Multiply by x.
489
00:30:29,470 --> 00:30:30,900
PROFESSOR: Multiply by x.
490
00:30:30,900 --> 00:30:31,730
Good.
491
00:30:31,730 --> 00:30:40,140
So if I take this and multiply
by x, i equals zero to n,
492
00:30:40,140 --> 00:30:49,060
ix to the i equals x minus
n plus 1, x to the n plus 1,
493
00:30:49,060 --> 00:30:56,240
plus nx to the n plus 2,
all over 1 minus x squared.
494
00:30:56,240 --> 00:30:57,887
OK?
495
00:30:57,887 --> 00:30:59,970
Which should be the same--
yeah-- the same formula
496
00:30:59,970 --> 00:31:01,776
we had up there.
497
00:31:01,776 --> 00:31:03,400
So that's called the
derivative method.
498
00:31:03,400 --> 00:31:05,525
You can start manipulating--
you treat these things
499
00:31:05,525 --> 00:31:09,230
as polynomials-- these sums--
and you start manipulating them
500
00:31:09,230 --> 00:31:10,930
like you would polynomials.
501
00:31:10,930 --> 00:31:13,670
In fact, there's a whole
branch of mathematics
502
00:31:13,670 --> 00:31:15,830
called generating functions
that we won't have time
503
00:31:15,830 --> 00:31:20,560
to do in this class that's
in chapter 12 of the text.
504
00:31:20,560 --> 00:31:24,426
But you do things
like that to get sums.
505
00:31:29,820 --> 00:31:33,430
Any questions about
what we did there?
506
00:31:33,430 --> 00:31:36,800
You can also do a version where
you take integrals of this
507
00:31:36,800 --> 00:31:39,260
if you want, and
then you get the i's
508
00:31:39,260 --> 00:31:41,708
in the denominator instead
of those coefficients.
509
00:31:45,340 --> 00:31:48,980
For homework, I
think we've given you
510
00:31:48,980 --> 00:31:52,761
the sum of i squared x to the i.
511
00:31:52,761 --> 00:31:56,640
How do you think you're
going to do that?
512
00:31:56,640 --> 00:31:59,220
Any thoughts about how
you're going to solve that?
513
00:31:59,220 --> 00:32:01,440
Get the sum, a closed
form for the sum of i
514
00:32:01,440 --> 00:32:04,160
squared x to the i?
515
00:32:04,160 --> 00:32:06,060
AUDIENCE: Do the
derivative method twice.
516
00:32:06,060 --> 00:32:07,268
PROFESSOR: Yeah, do it twice.
517
00:32:07,268 --> 00:32:08,946
Take this, which now you know.
518
00:32:08,946 --> 00:32:11,700
Take the derivative again.
519
00:32:11,700 --> 00:32:12,880
Won't be too hard.
520
00:32:18,530 --> 00:32:23,980
You can also take the version of
this where n goes to infinity.
521
00:32:23,980 --> 00:32:24,655
Let's do that.
522
00:32:30,120 --> 00:32:34,900
If the absolute value of x
is less than 1, the sum i
523
00:32:34,900 --> 00:32:41,820
equals 1 to infinity of ix to
the i, what does that equal?
524
00:32:44,560 --> 00:32:46,356
This one, you can see
it easier up here.
525
00:32:49,020 --> 00:32:53,890
What happens when
n goes to infinity?
526
00:32:53,890 --> 00:32:54,750
What does this do?
527
00:32:57,390 --> 00:32:59,570
X is less than 1,
an absolute value.
528
00:32:59,570 --> 00:33:02,920
What happens to this
as n goes to infinity?
529
00:33:02,920 --> 00:33:03,420
This term.
530
00:33:06,380 --> 00:33:09,010
Goes to 0, right?
531
00:33:09,010 --> 00:33:11,930
This gets big, but this
gets smaller faster.
532
00:33:11,930 --> 00:33:16,230
What happens to this term
as n goes to infinity?
533
00:33:16,230 --> 00:33:18,500
Same thing, 0.
534
00:33:18,500 --> 00:33:20,920
All I'm left with is x
over 1 minus x squared.
535
00:33:29,570 --> 00:33:32,930
Now, this formula
is useful if you're
536
00:33:32,930 --> 00:33:37,410
trying to, say, get
the value of a company,
537
00:33:37,410 --> 00:33:39,490
and the company is growing.
538
00:33:39,490 --> 00:33:44,850
Every year the company grows
its bottom line by m dollars.
539
00:33:44,850 --> 00:33:47,240
So the first year, the
company generates m dollars,
540
00:33:47,240 --> 00:33:50,060
the next year it generates
two m dollars in profit,
541
00:33:50,060 --> 00:33:52,136
the next year is
three m dollars.
542
00:33:52,136 --> 00:33:53,760
So you've got an
entity that every year
543
00:33:53,760 --> 00:33:55,260
is growing by a fixed amount.
544
00:33:55,260 --> 00:33:57,870
It's not doubling every
year, but every year
545
00:33:57,870 --> 00:34:00,760
adds in m dollars
more of profit.
546
00:34:00,760 --> 00:34:03,400
What would you pay
to buy that company?
547
00:34:03,400 --> 00:34:05,550
What is that worth?
548
00:34:05,550 --> 00:34:08,305
So you can think of this
as, again, an annuity.
549
00:34:13,900 --> 00:34:25,090
Here the annuity pays im
dollars, in this case,
550
00:34:25,090 --> 00:34:32,250
at the end, not the beginning,
say, of the year i forever.
551
00:34:39,070 --> 00:34:43,409
This company is-- or this
annuity-- is worth, well,
552
00:34:43,409 --> 00:34:46,190
we just plug into the formula.
553
00:34:46,190 --> 00:34:50,469
Instead of $1 each year, it's
m so there's an m out front.
554
00:34:50,469 --> 00:34:58,490
x is 1 over 1 plus p, and
then we have 1 minus 1 over 1
555
00:34:58,490 --> 00:34:59,714
plus p squared.
556
00:35:02,620 --> 00:35:06,840
And if we multiply the top and
bottom by 1 plus p squared,
557
00:35:06,840 --> 00:35:11,954
we get m 1 plus
p over p squared.
558
00:35:15,190 --> 00:35:17,816
So it's possible with
a very simple formula
559
00:35:17,816 --> 00:35:19,190
to figure out how
much you should
560
00:35:19,190 --> 00:35:22,730
spend to buy this company,
what its value is today.
561
00:35:22,730 --> 00:35:29,590
So, for example, say the company
was adding $50,000 a year
562
00:35:29,590 --> 00:35:31,650
in profit.
563
00:35:31,650 --> 00:35:37,300
The interest rate was 6%,
the value of this company
564
00:35:37,300 --> 00:35:45,510
is $14 million-- $14.7
million, just plugging
565
00:35:45,510 --> 00:35:47,960
into that formula.
566
00:35:47,960 --> 00:35:51,380
So people that buy
companies and stuff,
567
00:35:51,380 --> 00:35:55,494
they use formulas like this
to figure out what it's worth.
568
00:35:55,494 --> 00:35:56,910
Of course, you've
got to make sure
569
00:35:56,910 --> 00:36:01,704
it's really going to keep paying
the $50,000 more every year
570
00:36:01,704 --> 00:36:03,370
and that this is the
right interest rate
571
00:36:03,370 --> 00:36:05,465
to be thinking about.
572
00:36:05,465 --> 00:36:07,090
You know, and the
guys on Wall Street--
573
00:36:07,090 --> 00:36:08,631
the bankers on Wall
Street-- they all
574
00:36:08,631 --> 00:36:12,670
have their estimations for
what these things are--
575
00:36:12,670 --> 00:36:16,200
the value of p they would
put into these formulas.
576
00:36:16,200 --> 00:36:19,410
Any questions about that?
577
00:36:19,410 --> 00:36:20,715
Yeah.
578
00:36:20,715 --> 00:36:22,247
AUDIENCE: [INAUDIBLE]
579
00:36:22,247 --> 00:36:22,830
PROFESSOR: OK.
580
00:36:22,830 --> 00:36:24,290
Good.
581
00:36:24,290 --> 00:36:27,170
So this one is OK?
582
00:36:27,170 --> 00:36:28,040
OK.
583
00:36:28,040 --> 00:36:32,910
I plugged x equals
1 over 1 plus p,
584
00:36:32,910 --> 00:36:34,920
like we did before--
remember for the annuity--
585
00:36:34,920 --> 00:36:38,090
because every year
you're degrading it,
586
00:36:38,090 --> 00:36:40,430
devaluing by 1 over 1 plus p.
587
00:36:40,430 --> 00:36:47,160
So that's the x term, and it's
paying-- in the i-th year,
588
00:36:47,160 --> 00:36:51,400
it's paying im dollars.
589
00:36:51,400 --> 00:36:52,250
All right?
590
00:36:52,250 --> 00:36:56,470
So the first year it pays n
dollars, the next year 2 m,
591
00:36:56,470 --> 00:37:00,830
the next year 3 m,
the next year 4 m,
592
00:37:00,830 --> 00:37:03,310
but every year you're
knocking it down by 1 plus 1
593
00:37:03,310 --> 00:37:06,070
over p to the number of years.
594
00:37:06,070 --> 00:37:11,520
So what you get-- the sum
you've really got here--
595
00:37:11,520 --> 00:37:15,130
is i equals 1 to infinity,
im dollars are paid,
596
00:37:15,130 --> 00:37:18,300
but those dollars are
worth 1 over 1 plus p
597
00:37:18,300 --> 00:37:21,152
to the i today,
the current value.
598
00:37:21,152 --> 00:37:22,110
That's a good question.
599
00:37:22,110 --> 00:37:24,350
I should've said that.
600
00:37:24,350 --> 00:37:26,572
That's a great question.
601
00:37:26,572 --> 00:37:28,030
So that's how we
connected this up,
602
00:37:28,030 --> 00:37:31,130
because you're getting paid
this much in our years,
603
00:37:31,130 --> 00:37:33,390
and that's worth
that much degradation
604
00:37:33,390 --> 00:37:35,740
or that much devaluation
today, and now we
605
00:37:35,740 --> 00:37:38,930
add up a total current value.
606
00:37:38,930 --> 00:37:41,190
So even a company that is
paying you more and more
607
00:37:41,190 --> 00:37:47,220
every year still has a finite
value, because the extra--
608
00:37:47,220 --> 00:37:49,990
the payments are increasing
but only linearly.
609
00:37:49,990 --> 00:37:52,670
The value today is
decreasing geometrically,
610
00:37:52,670 --> 00:37:55,040
and the geometric decrease
wipes out the value
611
00:37:55,040 --> 00:37:56,600
of the company in the future.
612
00:37:56,600 --> 00:37:57,100
Yeah.
613
00:37:57,100 --> 00:38:01,810
AUDIENCE: Are you [? squaring ?]
quantity of [INAUDIBLE].
614
00:38:05,640 --> 00:38:06,780
PROFESSOR: What did I do?
615
00:38:06,780 --> 00:38:09,030
Oh, wait, wait, wait.
616
00:38:09,030 --> 00:38:12,380
I screwed up here too.
617
00:38:12,380 --> 00:38:14,661
Is that what you're
asking about?
618
00:38:14,661 --> 00:38:15,160
Yeah.
619
00:38:15,160 --> 00:38:16,743
That's what I should
have done, right?
620
00:38:16,743 --> 00:38:20,600
Because I got 1 minus x is
1 minus 1 over 1 plus p.
621
00:38:20,600 --> 00:38:25,970
That gets squared, and now when
I multiply 1 plus p squared,
622
00:38:25,970 --> 00:38:28,310
it's multiplying
this by 1 plus p.
623
00:38:28,310 --> 00:38:30,630
It's 1 plus p minus 1 is p.
624
00:38:30,630 --> 00:38:32,342
So I have p squared.
625
00:38:32,342 --> 00:38:33,550
All right, so this part's OK.
626
00:38:33,550 --> 00:38:35,610
That part I wrote wrong.
627
00:38:35,610 --> 00:38:36,280
That's good.
628
00:38:36,280 --> 00:38:37,130
Any other questions?
629
00:38:46,430 --> 00:38:47,771
So let's do a simple example.
630
00:39:03,230 --> 00:39:04,710
What is this sum?
631
00:39:14,026 --> 00:39:23,580
A 1/2 plus 2/4 plus
3/8 plus 4/16 forever.
632
00:39:23,580 --> 00:39:26,585
What's that sum equal?
633
00:39:32,970 --> 00:39:35,975
You can plug that
in the formula.
634
00:39:35,975 --> 00:39:38,060
AUDIENCE: [INAUDIBLE]
635
00:39:38,060 --> 00:39:40,440
PROFESSOR: Yeah.
636
00:39:40,440 --> 00:39:41,260
That's right.
637
00:39:41,260 --> 00:39:43,350
Good.
638
00:39:43,350 --> 00:39:46,310
These details.
639
00:39:46,310 --> 00:39:48,156
Otherwise that
sum would be what?
640
00:39:48,156 --> 00:39:50,640
If I didn't put
the negative here,
641
00:39:50,640 --> 00:39:53,510
it's going to be infinity,
and that's not so interesting.
642
00:39:53,510 --> 00:39:55,970
The negative makes it more
interesting, so I got 1 over 2
643
00:39:55,970 --> 00:39:57,810
to the i in there.
644
00:39:57,810 --> 00:39:58,785
What's it worth then?
645
00:40:01,790 --> 00:40:04,030
Well, I can plug in the formula.
646
00:40:04,030 --> 00:40:06,650
What's x?
647
00:40:06,650 --> 00:40:07,760
One half.
648
00:40:07,760 --> 00:40:16,740
So I get 1/2 over 1 minus
1/2 squared is 1/2 over 1/4,
649
00:40:16,740 --> 00:40:17,690
and that's 2.
650
00:40:24,710 --> 00:40:28,925
Any questions on that formula?
651
00:40:28,925 --> 00:40:31,280
It's amazing how useful
these things get to be later.
652
00:40:34,910 --> 00:40:39,130
So that's sort of the
geometric kinds of things.
653
00:40:39,130 --> 00:40:43,160
Next I want to talk about more
of the arithmetic kinds of sums
654
00:40:43,160 --> 00:40:45,440
and what you do there.
655
00:40:45,440 --> 00:40:49,210
In fact, we've already
seen one that we've done.
656
00:40:49,210 --> 00:40:55,100
If I sum i equals 1 to n of
i-- I think we've already
657
00:40:55,100 --> 00:40:59,500
done this one-- that's just
n times n plus 1 over 2,
658
00:40:59,500 --> 00:41:01,170
and probably most
of you even learned
659
00:41:01,170 --> 00:41:03,380
that formula back
in middle school,
660
00:41:03,380 --> 00:41:07,220
I'm guessing-- maybe before.
661
00:41:07,220 --> 00:41:09,825
How many people know
the answer for this sum?
662
00:41:15,000 --> 00:41:17,765
The sum of the squares--
the first n squares.
663
00:41:17,765 --> 00:41:18,390
Somebody knows.
664
00:41:18,390 --> 00:41:19,720
What is it?
665
00:41:19,720 --> 00:41:26,595
AUDIENCE: n times n plus 1
times 2n plus 1, all over 6.
666
00:41:26,595 --> 00:41:27,470
PROFESSOR: Very good.
667
00:41:27,470 --> 00:41:29,160
That is correct.
668
00:41:29,160 --> 00:41:31,450
Most people don't
remember that one.
669
00:41:31,450 --> 00:41:35,140
It's a little harder to derive.
670
00:41:35,140 --> 00:41:39,410
How would you prove
this by induction?
671
00:41:39,410 --> 00:41:41,200
Unfortunately, induction
doesn't tell you
672
00:41:41,200 --> 00:41:44,260
how to remember what
the formula was,
673
00:41:44,260 --> 00:41:47,700
and there's a couple of
ways you can go about that.
674
00:41:47,700 --> 00:41:50,460
One is, you can
remember or guess
675
00:41:50,460 --> 00:41:53,222
that the answer is
a polynomial in n.
676
00:41:53,222 --> 00:41:55,710
In fact, because
you're summing squares,
677
00:41:55,710 --> 00:42:00,100
you might guess that it's
a cubic polynomial in n,
678
00:42:00,100 --> 00:42:03,890
and if you remember just that
or guess just that, then you
679
00:42:03,890 --> 00:42:08,540
could actually plug in
values and get the answer.
680
00:42:08,540 --> 00:42:10,870
And this is-- you
know, a common method
681
00:42:10,870 --> 00:42:12,850
of solving these sums
is you sort of guess
682
00:42:12,850 --> 00:42:15,010
the form of the solution.
683
00:42:15,010 --> 00:42:23,760
In this case you might
guess that for all n,
684
00:42:23,760 --> 00:42:29,166
the sum i equals 1 to n of
i squared equals a cubic.
685
00:42:34,730 --> 00:42:41,380
And then what you would do is
plug in the value n equals 1,
686
00:42:41,380 --> 00:42:43,860
n equals 2, maybe
even-- we'll make
687
00:42:43,860 --> 00:42:47,350
it n equals 0-- make
it simple and start
688
00:42:47,350 --> 00:42:51,380
getting some constraints
on the coefficients.
689
00:42:51,380 --> 00:42:59,176
If you would plug in n
equals 0, the sum is 0.
690
00:43:02,300 --> 00:43:06,250
The polynomial evaluates to d.
691
00:43:06,250 --> 00:43:10,160
That tells you what d has got
to be right away. n equals 1.
692
00:43:10,160 --> 00:43:14,050
The sum is 1, and when you
plug into the polynomial,
693
00:43:14,050 --> 00:43:18,760
you get a plus b plus c plus d.
694
00:43:18,760 --> 00:43:21,540
n equals 2.
695
00:43:21,540 --> 00:43:26,710
Well, that's 1 plus
4 is 5, 2 cubed is 8,
696
00:43:26,710 --> 00:43:32,680
so you have 8a plus
4b plus 2c plus d,
697
00:43:32,680 --> 00:43:36,720
and you'll need one more since
you've got four variables.
698
00:43:36,720 --> 00:43:40,950
Let's see, 1 plus
4 plus 9 is 14.
699
00:43:40,950 --> 00:43:50,690
I've now got 3 cubed is
27a plus 9b plus 3c plus d.
700
00:43:50,690 --> 00:43:54,120
So now I've got four
equations and four variables
701
00:43:54,120 --> 00:43:57,360
and, with any luck, I can
solve that system of equations
702
00:43:57,360 --> 00:43:58,930
and get the answer.
703
00:43:58,930 --> 00:44:00,090
And, in fact, you can.
704
00:44:00,090 --> 00:44:07,300
When you solve this system, you
get a equals 1/3, b equals 1/2,
705
00:44:07,300 --> 00:44:11,460
c equals 1/6, and d equals 0.
706
00:44:11,460 --> 00:44:14,970
And that's exactly what
you get in that formula.
707
00:44:14,970 --> 00:44:19,650
So that's a way to reproduce
the formula if you forgot it.
708
00:44:19,650 --> 00:44:23,410
Now, this method--
really to be sure you
709
00:44:23,410 --> 00:44:25,920
got the right answer--
you've got to go prove it
710
00:44:25,920 --> 00:44:30,572
by induction, because I
derived the answer-- if it
711
00:44:30,572 --> 00:44:32,530
was a polynomial, I would
have gotten it right,
712
00:44:32,530 --> 00:44:34,169
but I might be
wrong in my guess.
713
00:44:34,169 --> 00:44:35,710
And to make sure
your guess is right,
714
00:44:35,710 --> 00:44:37,335
you've got to go back
and use induction
715
00:44:37,335 --> 00:44:38,762
to prove it for this approach.
716
00:44:38,762 --> 00:44:39,262
Yeah.
717
00:44:39,262 --> 00:44:41,981
AUDIENCE: How do you know that
it would be [INAUDIBLE] and not
718
00:44:41,981 --> 00:44:43,160
some higher power?
719
00:44:43,160 --> 00:44:45,710
PROFESSOR: Well, it turns
out that anytime you're
720
00:44:45,710 --> 00:44:49,630
summing powers, the answer
is a polynomial to one
721
00:44:49,630 --> 00:44:51,540
higher degree.
722
00:44:51,540 --> 00:44:54,750
So if you just remembered that
fact, or you guessed that fact.
723
00:44:54,750 --> 00:44:58,000
Another way to sort of
imagine that might be true
724
00:44:58,000 --> 00:45:01,120
is that I'm getting
n of them, so I
725
00:45:01,120 --> 00:45:04,500
might be multiplying--
the top one is n squared,
726
00:45:04,500 --> 00:45:07,900
so I'm going to have n
of them about n squared.
727
00:45:07,900 --> 00:45:11,370
Might be something like n cubed.
728
00:45:11,370 --> 00:45:16,660
That's another way you could
think of it, to guess that.
729
00:45:16,660 --> 00:45:20,186
Any other questions on this?
730
00:45:25,130 --> 00:45:29,970
So far, all these sums had nice
closed forms, and a lot of them
731
00:45:29,970 --> 00:45:33,410
do that you'll encounter
later on, but not all,
732
00:45:33,410 --> 00:45:37,580
and sometimes you get sums that
don't have a nice closed form--
733
00:45:37,580 --> 00:45:39,670
at least nobody has
ever figured out one,
734
00:45:39,670 --> 00:45:42,560
and probably doesn't
always exist.
735
00:45:42,560 --> 00:45:46,820
For example, what if I
want to sum the first n
736
00:45:46,820 --> 00:45:48,840
square roots of integers?
737
00:45:53,340 --> 00:45:54,774
Let's write that down.
738
00:46:04,400 --> 00:46:07,618
So say I want a closed
form for this guy.
739
00:46:13,560 --> 00:46:17,340
Nobody knows an answer
for that, but there
740
00:46:17,340 --> 00:46:22,000
are ways of getting very
good, close bounds on it that
741
00:46:22,000 --> 00:46:23,950
are closed form, and
these are very important,
742
00:46:23,950 --> 00:46:26,060
and we're going to use
this the rest of today
743
00:46:26,060 --> 00:46:27,890
and the rest of next time.
744
00:46:27,890 --> 00:46:32,740
And they're based on replacing
the sum with an integral,
745
00:46:32,740 --> 00:46:35,140
and the integral is very
close to the right answer,
746
00:46:35,140 --> 00:46:37,820
and then we can see what
the error terms are.
747
00:46:37,820 --> 00:46:39,580
So let's first look
at the case when
748
00:46:39,580 --> 00:46:42,560
we've got a sum where the
terms are increasing as i
749
00:46:42,560 --> 00:46:54,240
grows, and we'll call
these integration bounds,
750
00:46:54,240 --> 00:46:57,790
and a general sum will look
like this-- i equals 1 to n
751
00:46:57,790 --> 00:47:04,870
of f of i, and the first case is
when f is a positive increasing
752
00:47:04,870 --> 00:47:13,150
function, increasing in i.
753
00:47:20,660 --> 00:47:22,960
Integration bounds, and so
we're increasing function.
754
00:47:28,160 --> 00:47:31,530
So let me draw a picture
that will hopefully
755
00:47:31,530 --> 00:47:34,060
make the bounds that we're
going to get pretty easy.
756
00:47:47,550 --> 00:47:53,590
So let's draw the
sum here as follows.
757
00:47:53,590 --> 00:48:04,360
I've got 0, 1, 2, 3, n
minus 2, n minus 1, n,
758
00:48:04,360 --> 00:48:06,840
and draw the values of f here.
759
00:48:06,840 --> 00:48:17,260
Here's f of 1, f of 2--
it's increasing-- f of 3,
760
00:48:17,260 --> 00:48:19,550
f of n minus 1, and f of n.
761
00:48:23,180 --> 00:48:27,630
Then I'll draw the
rectangles here.
762
00:48:31,640 --> 00:48:38,620
So this has area of f of
1, this has area f of 2,
763
00:48:38,620 --> 00:48:43,630
this has area f of 3,
and we keep on going.
764
00:48:43,630 --> 00:48:47,070
Let's see, this will
be f of n minus 2
765
00:48:47,070 --> 00:48:50,775
on this one-- I'll just do f of
n minus 1, draw this guy here.
766
00:48:53,950 --> 00:48:56,670
So its unit width, its
height is f of n minus 1,
767
00:48:56,670 --> 00:49:03,136
so its area is f of n
minus 1, and then f of n.
768
00:49:05,690 --> 00:49:11,240
And let me also--
so the sum of f of i
769
00:49:11,240 --> 00:49:14,500
is the areas in the rectangles.
770
00:49:14,500 --> 00:49:16,760
That's what the
sum is, and I want
771
00:49:16,760 --> 00:49:21,120
to get bounds on this
sum using the integral,
772
00:49:21,120 --> 00:49:23,510
because integrals are
easier to compute.
773
00:49:23,510 --> 00:49:28,740
So let's draw the function
f of x from 1 to n.
774
00:49:35,720 --> 00:49:39,765
All right, so this is
f of x as a function.
775
00:49:42,380 --> 00:49:51,910
Now I claim that the sum
i equals 1 to n of f of i
776
00:49:51,910 --> 00:49:57,610
is at least f of 1 plus
the integral from 1 to n,
777
00:49:57,610 --> 00:49:58,870
f of x, dx.
778
00:50:01,570 --> 00:50:07,590
Now, the integral
from 1 to n of f of x
779
00:50:07,590 --> 00:50:10,786
is this stuff, the
stuff under the curve.
780
00:50:10,786 --> 00:50:14,930
It comes down here,
starts at 1, and it's
781
00:50:14,930 --> 00:50:17,760
the stuff under the curve.
782
00:50:17,760 --> 00:50:19,410
And what I'm saying
here is that if you
783
00:50:19,410 --> 00:50:21,490
take that stuff under
the curve and add
784
00:50:21,490 --> 00:50:25,000
f of 1, which is
this piece, that's
785
00:50:25,000 --> 00:50:28,230
a lower bound on our sum.
786
00:50:28,230 --> 00:50:31,140
The sum's bigger than that.
787
00:50:31,140 --> 00:50:34,620
So what I'm saying is the
area in the rectangles
788
00:50:34,620 --> 00:50:38,440
is at least as big as the
area in the first rectangle
789
00:50:38,440 --> 00:50:42,250
plus the area under the curve.
790
00:50:42,250 --> 00:50:45,190
Does everybody see why that is?
791
00:50:45,190 --> 00:50:49,340
I'm saying the sum is the
area in the rectangles, right?
792
00:50:49,340 --> 00:50:51,050
That's pretty clear.
793
00:50:51,050 --> 00:50:56,760
And that is at least as big
as the first rectangle f of 1
794
00:50:56,760 --> 00:51:00,730
plus the stuff under the
curve, which is the integral,
795
00:51:00,730 --> 00:51:03,040
and I've left-- I've
chopped off these guys.
796
00:51:03,040 --> 00:51:04,500
That's extra.
797
00:51:04,500 --> 00:51:06,410
OK?
798
00:51:06,410 --> 00:51:07,710
Is that all right?
799
00:51:07,710 --> 00:51:10,200
So lower bound.
800
00:51:10,200 --> 00:51:12,510
Any questions on
the lower bound?
801
00:51:12,510 --> 00:51:16,120
This is a picture proof, which
we always tell you not to do,
802
00:51:16,120 --> 00:51:18,456
but we're going to do one here.
803
00:51:21,830 --> 00:51:26,119
And, of course, it totally hides
why did I need f is increasing,
804
00:51:26,119 --> 00:51:27,410
but we'll see that in a minute.
805
00:51:27,410 --> 00:51:29,936
The proof would not work
unless it is increasing here.
806
00:51:32,840 --> 00:51:34,340
Any questions,
because now going I'm
807
00:51:34,340 --> 00:51:37,390
going to do the other
bound, the other side.
808
00:51:37,390 --> 00:51:41,300
I also claim-- this will be
a little trickier to see--
809
00:51:41,300 --> 00:51:49,230
that the sum is at most f of n
plus the integral from 1 to n.
810
00:51:53,420 --> 00:51:56,110
So this is the lower
bound add in f of 1,
811
00:51:56,110 --> 00:51:57,810
the upper bound
just add in f of n.
812
00:51:57,810 --> 00:52:00,440
So let's see why that's true.
813
00:52:00,440 --> 00:52:03,140
Now, to see that,
this is-- I'm not
814
00:52:03,140 --> 00:52:05,400
going to be able to draw it.
815
00:52:05,400 --> 00:52:08,420
I want you to imagine taking
this curve and the area
816
00:52:08,420 --> 00:52:16,480
under it, down to here, and
sliding it left one unit.
817
00:52:16,480 --> 00:52:23,967
sliding it left to here, sliding
it left one unit over to here.
818
00:52:26,950 --> 00:52:30,980
Now, when I slide it left one
unit, did the area under it
819
00:52:30,980 --> 00:52:33,750
change?
820
00:52:33,750 --> 00:52:34,280
No.
821
00:52:34,280 --> 00:52:36,860
It's the same area
under it, just where
822
00:52:36,860 --> 00:52:39,790
it sits on the picture
is now out here.
823
00:52:42,950 --> 00:52:45,320
It's this area under this
guy, but it's the same thing,
824
00:52:45,320 --> 00:52:47,300
its the same integral.
825
00:52:47,300 --> 00:52:50,680
And you can see that
it's more than what's
826
00:52:50,680 --> 00:52:55,110
in these rectangles, because
I got all this stuff.
827
00:52:55,110 --> 00:52:57,050
And, of course, I didn't
even include this,
828
00:52:57,050 --> 00:53:01,040
so now I add the f n.
829
00:53:01,040 --> 00:53:04,640
So if I take the area under the
curve, which is the integral,
830
00:53:04,640 --> 00:53:06,450
shift it left one,
so it only goes up
831
00:53:06,450 --> 00:53:11,100
to here now, and then add in
this rectangle, that dominates
832
00:53:11,100 --> 00:53:14,590
the area in the rectangles.
833
00:53:14,590 --> 00:53:15,110
Bigger than.
834
00:53:18,890 --> 00:53:19,791
Do you see that?
835
00:53:23,271 --> 00:53:25,020
I could do a lot of
equations on the board
836
00:53:25,020 --> 00:53:29,550
but, for sure, that would
be hopeless to follow.
837
00:53:29,550 --> 00:53:31,160
Any questions about this?
838
00:53:31,160 --> 00:53:31,896
Yeah.
839
00:53:31,896 --> 00:53:35,088
AUDIENCE: I guess I understand
the lower amounts because we're
840
00:53:35,088 --> 00:53:36,460
cutting off the triangles.
841
00:53:36,460 --> 00:53:38,360
PROFESSOR: Yeah.
842
00:53:38,360 --> 00:53:42,760
But is there-- is it
a lot of hand waving,
843
00:53:42,760 --> 00:53:45,660
or am I just missing something,
that it's always going to be
844
00:53:45,660 --> 00:53:48,004
the f of n is what we--
845
00:53:48,004 --> 00:53:48,670
PROFESSOR: Yeah.
846
00:53:48,670 --> 00:53:50,750
There's a little
hand waving going on,
847
00:53:50,750 --> 00:53:53,076
but I do believe it is true.
848
00:53:53,076 --> 00:53:54,700
With equations you
can make it precise.
849
00:53:54,700 --> 00:53:57,876
Let's look at it again,
do this one more time.
850
00:53:57,876 --> 00:53:59,482
AUDIENCE: [INAUDIBLE]
851
00:53:59,482 --> 00:54:01,440
PROFESSOR: Yeah, I'm
waving hands a little bit,
852
00:54:01,440 --> 00:54:04,940
but it also-- hopefully
the intuition comes across,
853
00:54:04,940 --> 00:54:10,220
because when I
shift left by one,
854
00:54:10,220 --> 00:54:13,230
this point becomes this
point, and that point becomes
855
00:54:13,230 --> 00:54:16,300
that point, and
I'm catching sort
856
00:54:16,300 --> 00:54:24,300
of the cusp of these rectangles,
and now I take this curve here,
857
00:54:24,300 --> 00:54:28,120
shifting the whole
curve left one unit,
858
00:54:28,120 --> 00:54:30,430
and the area doesn't change.
859
00:54:30,430 --> 00:54:33,010
It would be equivalent of
taking the integral from 0
860
00:54:33,010 --> 00:54:35,170
to n minus 1.
861
00:54:35,170 --> 00:54:38,809
You notice what I'm
doing-- of f of x plus 1.
862
00:54:38,809 --> 00:54:40,850
There's another way to
look at it mathematically,
863
00:54:40,850 --> 00:54:43,410
maybe-- probably the
formal way to do it--
864
00:54:43,410 --> 00:54:46,060
but the idea is that
this now contains
865
00:54:46,060 --> 00:54:48,580
all these first n
minus 1 rectangles,
866
00:54:48,580 --> 00:54:51,180
are contained underneath it.
867
00:54:51,180 --> 00:54:55,580
And then I just add this
in, and I'm good to go.
868
00:54:55,580 --> 00:54:57,370
I've contained all
the rectangles now
869
00:54:57,370 --> 00:55:00,577
for the upper bounds.
870
00:55:00,577 --> 00:55:02,035
All right,
mathematically what this
871
00:55:02,035 --> 00:55:06,270
is, this curve is
0 to n minus 1,
872
00:55:06,270 --> 00:55:10,570
fx plus 1, which is the
same thing as what that is.
873
00:55:13,810 --> 00:55:19,180
Any questions for that?
874
00:55:19,180 --> 00:55:23,160
But now I have good
bounds on the sum.
875
00:55:23,160 --> 00:55:28,100
We know that the sum is at
least this and at most that,
876
00:55:28,100 --> 00:55:33,990
and those two bounds only differ
by a single term in the sum,
877
00:55:33,990 --> 00:55:36,124
so they're very close.
878
00:55:36,124 --> 00:55:38,040
These actually are good
formulas to write down
879
00:55:38,040 --> 00:55:38,873
for your crib sheet.
880
00:55:38,873 --> 00:55:48,880
That is worth doing on the test,
and we'll use them more today,
881
00:55:48,880 --> 00:55:51,333
and we'll also use
them on Thursday.
882
00:55:56,730 --> 00:55:59,400
So now we can actually
get close bounds
883
00:55:59,400 --> 00:56:02,850
on the sum of the square roots.
884
00:56:02,850 --> 00:56:06,365
So let's see how
this works for f
885
00:56:06,365 --> 00:56:11,120
of i equal to the square root
of i, which is increasing.
886
00:56:11,120 --> 00:56:17,470
So I compute the integral from
1 to n of square root of x dx,
887
00:56:17,470 --> 00:56:24,960
and that's just x to the 3/2
over 3/2, evaluated at n and 1,
888
00:56:24,960 --> 00:56:32,660
and that just equals 2/3
n to the 3/2 minus 1.
889
00:56:32,660 --> 00:56:35,820
And now I can compute
the bounds on the sum
890
00:56:35,820 --> 00:56:37,160
of the first n square roots.
891
00:56:39,920 --> 00:56:47,750
So I know that square root
i equals 1 to n-- well,
892
00:56:47,750 --> 00:56:57,000
the upper bound is f
n plus the integral,
893
00:56:57,000 --> 00:57:02,204
and the lower bound is f
of 1 plus the integral.
894
00:57:07,590 --> 00:57:09,390
What is f of n?
895
00:57:12,280 --> 00:57:15,150
That's the square root of n.
896
00:57:15,150 --> 00:57:18,330
What is f of 1?
897
00:57:18,330 --> 00:57:21,860
The square root
of 1, which is 1.
898
00:57:21,860 --> 00:57:24,310
So I'll plug that in here.
899
00:57:24,310 --> 00:57:34,440
I get 2/3 n to the 3/2 plus
1 minus 2/3 is plus 1/3,
900
00:57:34,440 --> 00:57:41,020
and here I get 2/3 n to the
3/2 plus the square root
901
00:57:41,020 --> 00:57:42,798
of n minus 2/3.
902
00:57:46,210 --> 00:57:49,840
So now I have pretty good
bounds on the sum of the first n
903
00:57:49,840 --> 00:57:54,320
square roots using this method.
904
00:57:54,320 --> 00:58:03,180
So for example,
take n equals 100.
905
00:58:03,180 --> 00:58:07,270
This number evaluates to 667.
906
00:58:07,270 --> 00:58:12,130
This number evaluates to
676, and the difference
907
00:58:12,130 --> 00:58:16,290
is 9, which is the square
root of 100 minus 1.
908
00:58:16,290 --> 00:58:20,010
This is the square
root of n, this is 1,
909
00:58:20,010 --> 00:58:24,210
so the gap here, square root
of n minus 1, and n equals 100.
910
00:58:24,210 --> 00:58:26,430
Square root of 100 minus
1 is 9, so I shouldn't be
911
00:58:26,430 --> 00:58:28,642
surprised my gap here is nine.
912
00:58:28,642 --> 00:58:30,350
So I didn't get exactly
the right answer,
913
00:58:30,350 --> 00:58:33,055
but I'm pretty close here.
914
00:58:36,030 --> 00:58:44,670
Now, as n grows, what happens to
the gap between the upper bound
915
00:58:44,670 --> 00:58:47,820
and the lower bound?
916
00:58:47,820 --> 00:58:49,370
What does it do?
917
00:58:49,370 --> 00:58:51,000
It gets bigger.
918
00:58:51,000 --> 00:58:53,010
So my gap gets bigger.
919
00:58:53,010 --> 00:58:54,490
That's not so nice.
920
00:58:54,490 --> 00:58:59,610
Doesn't always stay 9
forever, but somehow
921
00:58:59,610 --> 00:59:04,890
though this is still pretty
good, because the gap grows
922
00:59:04,890 --> 00:59:09,420
but the gap only grows
as square root of n,
923
00:59:09,420 --> 00:59:14,670
where the answer-- the bounds--
are growing as n to the 3/2.
924
00:59:14,670 --> 00:59:19,500
In other words, my error
is somewhere around here,
925
00:59:19,500 --> 00:59:23,150
and that gets smaller
compared to my answer, which
926
00:59:23,150 --> 00:59:25,970
is somewhere around there.
927
00:59:25,970 --> 00:59:30,010
And there's a special
notation that people use.
928
00:59:30,010 --> 00:59:33,491
In fact, let's write that
down and then do the notation.
929
00:59:45,570 --> 00:59:54,440
Another way of writing this is
that the sum i equals 1 to n
930
00:59:54,440 --> 00:59:56,820
of square root of i.
931
00:59:56,820 --> 01:00:02,670
The leading term here
is 2/3 n to the 3/2,
932
01:00:02,670 --> 01:00:05,630
and then there's some error
term-- delta term here.
933
01:00:05,630 --> 01:00:09,830
We'll call that
delta n, and we know
934
01:00:09,830 --> 01:00:19,169
that the error term is at
least 1/3 and, at most,
935
01:00:19,169 --> 01:00:20,460
the square root of n minus 2/3.
936
01:00:25,100 --> 01:00:29,090
So this delta term is bound
by the square root of n.
937
01:00:29,090 --> 01:00:31,220
That's getting
bigger as n gets big,
938
01:00:31,220 --> 01:00:36,920
but this value compared to
your answer is getting small.
939
01:00:36,920 --> 01:00:41,969
That's nice, and so the way that
gets represented is as follows.
940
01:00:41,969 --> 01:00:43,885
We would say-- it's using
that tilde notation.
941
01:00:46,620 --> 01:00:51,960
We write tilde 2/3
times n to the 3/2,
942
01:00:51,960 --> 01:00:53,620
and now we've gotten
rid of the delta,
943
01:00:53,620 --> 01:00:55,830
because this tilde is
telling us that everything
944
01:00:55,830 --> 01:01:01,500
else out here gets small
compared to this as n gets big.
945
01:01:01,500 --> 01:01:04,260
And the formal definition--
Let's write out
946
01:01:04,260 --> 01:01:06,031
the formal definition for it.
947
01:01:22,720 --> 01:01:24,670
Now, a lot of times
you'll see people
948
01:01:24,670 --> 01:01:27,170
use this symbol to mean about.
949
01:01:27,170 --> 01:01:28,790
That's informal.
950
01:01:28,790 --> 01:01:31,975
When I'm using it here,
it's a very formal meaning
951
01:01:31,975 --> 01:01:32,600
mathematically.
952
01:01:35,580 --> 01:01:42,930
A function g of x is
tilde, a function h of x
953
01:01:42,930 --> 01:01:56,840
means that the limit as x goes
to infinity of g over h is 1.
954
01:01:56,840 --> 01:01:58,750
In other words, that
as x goes to infinity--
955
01:01:58,750 --> 01:02:04,480
as x gets big-- the ratio
of these guys becomes 1.
956
01:02:04,480 --> 01:02:05,990
And let's see if
that's true here.
957
01:02:09,040 --> 01:02:12,930
Well, square root
of i equals this,
958
01:02:12,930 --> 01:02:17,730
so I need to show the limit
of this over that is 1.
959
01:02:17,730 --> 01:02:20,550
So let's check that.
960
01:02:20,550 --> 01:02:26,360
A limit as n goes to
infinity of 2/3 n to the 3/2
961
01:02:26,360 --> 01:02:33,710
plus that delta term
over 2/3 n to the 3/2.
962
01:02:33,710 --> 01:02:38,565
Well, that equals-- divide out
by 2/3 n to the 3/2, I get a 1.
963
01:02:45,776 --> 01:02:47,150
Did I-- should I
have subtracted?
964
01:02:47,150 --> 01:02:49,830
No, that's OK.
965
01:02:49,830 --> 01:02:57,850
One plus delta n over
2/3 n to the 3/2.
966
01:02:57,850 --> 01:03:02,090
If I can pull the 1 out front,
that's 1 plus the limit,
967
01:03:02,090 --> 01:03:05,840
and this is now delta n is
at most square root of n,
968
01:03:05,840 --> 01:03:11,860
so I get square root of
n over 2/3 n to the 3/2.
969
01:03:11,860 --> 01:03:17,110
Square root of n over n to
the 3/2, that goes to 0.
970
01:03:17,110 --> 01:03:18,530
So this equals 1.
971
01:03:22,280 --> 01:03:24,440
So this limit is 1,
and so therefore I
972
01:03:24,440 --> 01:03:28,140
can say that the sum of
the first n square roots
973
01:03:28,140 --> 01:03:32,500
is tilde 2/3 n to the 3/2.
974
01:03:32,500 --> 01:03:35,320
Any questions about this?
975
01:03:35,320 --> 01:03:38,050
We're going to do a lot of this
kind of notation next time.
976
01:03:38,050 --> 01:03:39,190
Yeah.
977
01:03:39,190 --> 01:03:40,690
AUDIENCE: When you
took the integral
978
01:03:40,690 --> 01:03:44,460
and got 2/3 into
the 3/2 minus 1,
979
01:03:44,460 --> 01:03:49,050
why did the minus 1 not become
part of the actual solution
980
01:03:49,050 --> 01:03:51,317
and become part of the delta?
981
01:03:51,317 --> 01:03:51,900
PROFESSOR: OK.
982
01:03:51,900 --> 01:03:54,500
So you brought it
up to here, right?
983
01:03:54,500 --> 01:03:55,360
OK.
984
01:03:55,360 --> 01:03:59,410
So then I plug that
into the integral that
985
01:03:59,410 --> 01:04:01,790
appears on both sides here,
and here I add the f 1,
986
01:04:01,790 --> 01:04:06,439
here I add f n, and now I
have the lower bound here
987
01:04:06,439 --> 01:04:07,480
and the upper bound here.
988
01:04:07,480 --> 01:04:09,090
Are you good with those?
989
01:04:09,090 --> 01:04:09,590
All right.
990
01:04:09,590 --> 01:04:12,880
Now some judgment takes
place, and what I'm really
991
01:04:12,880 --> 01:04:17,590
trying to do here is figure out
what are the important terms
992
01:04:17,590 --> 01:04:20,250
in these bounds as n gets big?
993
01:04:20,250 --> 01:04:23,440
How big is this
growing as n gets big?
994
01:04:23,440 --> 01:04:28,350
Well, as n gets big, the
1/3 is not doing much.
995
01:04:28,350 --> 01:04:30,730
As n gets big, the
square root of n
996
01:04:30,730 --> 01:04:34,370
grows, but it's nothing
like what's happening here.
997
01:04:34,370 --> 01:04:35,820
If you had to
describe to somebody
998
01:04:35,820 --> 01:04:40,491
what's going on in this bound,
would you start here or here?
999
01:04:40,491 --> 01:04:40,990
No.
1000
01:04:40,990 --> 01:04:41,698
You'd start here.
1001
01:04:41,698 --> 01:04:44,750
This is the action, and there's
a little bit-- the rest is just
1002
01:04:44,750 --> 01:04:46,600
in the slop, in the air.
1003
01:04:46,600 --> 01:04:51,080
And so now I've used judgement
to say that delta is somewhere
1004
01:04:51,080 --> 01:04:53,414
in this stuff here.
1005
01:04:53,414 --> 01:04:55,830
What's really happening, and
the nice thing is they match.
1006
01:04:55,830 --> 01:04:59,770
The lower bound and the upper
bound match on that term.
1007
01:04:59,770 --> 01:05:04,750
So what I do is I write
it equals this term
1008
01:05:04,750 --> 01:05:10,390
plus something that's
smaller and, in particular,
1009
01:05:10,390 --> 01:05:14,080
it's between 1/3 and
square root of n minus 2/3.
1010
01:05:14,080 --> 01:05:14,780
All right.
1011
01:05:14,780 --> 01:05:16,890
So what I'm trying
to capture here
1012
01:05:16,890 --> 01:05:20,730
is just the guts of what's
happening to this function
1013
01:05:20,730 --> 01:05:24,530
as n grows, and the
guts of it is this.
1014
01:05:24,530 --> 01:05:28,210
It's not exactly equal to
2/3 times n to the 3/2,
1015
01:05:28,210 --> 01:05:30,440
but it's close
and, in fact, if I
1016
01:05:30,440 --> 01:05:34,930
take the limit of this over
that, that limit goes to 1.
1017
01:05:34,930 --> 01:05:39,260
It's a way of saying they're
approximately the same that's
1018
01:05:39,260 --> 01:05:41,980
called asymptotically
the same, and we'll
1019
01:05:41,980 --> 01:05:45,150
talk a lot more about
asymptotic notation next time.
1020
01:05:45,150 --> 01:05:49,214
We'll give you five more symbols
besides tilde that people use.
1021
01:05:51,900 --> 01:05:54,670
Any questions about-- maybe
start with the bounds.
1022
01:05:54,670 --> 01:05:57,110
Any question on the
bounds that we got?
1023
01:05:57,110 --> 01:06:01,790
That's the integration method,
first getting the bounds.
1024
01:06:01,790 --> 01:06:05,650
You take the integral, you add
f of 1 for the lower bound,
1025
01:06:05,650 --> 01:06:07,974
you add f of n for
the upper bound,
1026
01:06:07,974 --> 01:06:09,640
and it's in between,
somewhere in there.
1027
01:06:12,570 --> 01:06:14,960
Questions there?
1028
01:06:14,960 --> 01:06:15,470
All right.
1029
01:06:15,470 --> 01:06:18,590
Then we plugged
it in, and now we
1030
01:06:18,590 --> 01:06:22,149
look at this tilde notation
that says-- well, first we'd
1031
01:06:22,149 --> 01:06:22,940
write it like this.
1032
01:06:22,940 --> 01:06:27,390
The sum is this value plus an
error term and, lo and behold,
1033
01:06:27,390 --> 01:06:30,840
that error term is small.
1034
01:06:30,840 --> 01:06:34,480
If I take the limit of the whole
thing divided by the big term,
1035
01:06:34,480 --> 01:06:38,780
I get 1, which means this
thing is really not important.
1036
01:06:38,780 --> 01:06:39,732
So I write this.
1037
01:06:42,630 --> 01:06:45,840
Questions on that?
1038
01:06:45,840 --> 01:06:48,500
All right.
1039
01:06:48,500 --> 01:06:51,375
There's one more
case to consider,
1040
01:06:51,375 --> 01:06:53,750
and now we're going to go back
to the integration bounds,
1041
01:06:53,750 --> 01:06:57,557
and that is when f is
a decreasing function,
1042
01:06:57,557 --> 01:06:59,390
and we're going to do
the analysis for that,
1043
01:06:59,390 --> 01:07:00,515
and then we'll be all done.
1044
01:07:04,480 --> 01:07:09,740
So we're going to look
at integration bounds
1045
01:07:09,740 --> 01:07:13,670
when f is decreasing
and positive still.
1046
01:07:25,660 --> 01:07:34,810
The example here might
be, for example, the sum i
1047
01:07:34,810 --> 01:07:40,260
equals 1 to n, 1 over
the square root of i.
1048
01:07:40,260 --> 01:07:43,550
Say you had to get some idea
of how fast that function is
1049
01:07:43,550 --> 01:07:45,970
growing as a function of n.
1050
01:07:45,970 --> 01:07:52,996
I'm summing the first n
inverse as the square roots.
1051
01:07:52,996 --> 01:07:54,370
What is that
roughly going to be?
1052
01:07:54,370 --> 01:07:57,860
How fast does that grow
as a function of n?
1053
01:07:57,860 --> 01:07:58,981
So let's do that.
1054
01:08:02,256 --> 01:08:03,880
And, of course, 1
over square root of i
1055
01:08:03,880 --> 01:08:08,500
decreases as i gets bigger.
1056
01:08:08,500 --> 01:08:15,990
So let's do the general picture
again and see what happens.
1057
01:08:15,990 --> 01:08:28,790
So we have 0, 1, 2, 3, n minus
2, n minus 1, n, and now f of n
1058
01:08:28,790 --> 01:08:43,090
is the small term and f of n
minus 1, f of 3 here, f of 1.
1059
01:08:43,090 --> 01:08:45,250
Now, I'm going to
draw the rectangle.
1060
01:08:45,250 --> 01:08:49,470
This has area f of 1.
1061
01:08:49,470 --> 01:08:52,182
This one has area f of 2.
1062
01:08:55,080 --> 01:09:03,130
This one has area f of
3, and then this one
1063
01:09:03,130 --> 01:09:14,279
has area f of n minus 1 here,
and then, lastly, area f of n.
1064
01:09:14,279 --> 01:09:18,819
So the sum is the area in the
rectangles, just like before,
1065
01:09:18,819 --> 01:09:22,020
except now the rectangles
are getting smaller.
1066
01:09:22,020 --> 01:09:27,350
Let's draw the integral
like we did before.
1067
01:09:27,350 --> 01:09:32,380
The integral is the area
under this curve, f of x here,
1068
01:09:32,380 --> 01:09:33,362
just like before.
1069
01:09:35,960 --> 01:09:39,114
So this is f of x,
only it's decreasing.
1070
01:09:41,840 --> 01:09:49,670
Now, let's take the area under
this curve, and add f of 1
1071
01:09:49,670 --> 01:09:51,540
to it.
1072
01:09:51,540 --> 01:09:54,910
If I take the area under
this curve, all the way
1073
01:09:54,910 --> 01:10:00,780
down to here and then add
f of 1, what do I get?
1074
01:10:04,440 --> 01:10:07,791
Upper bound on my sum.
1075
01:10:07,791 --> 01:10:08,290
OK.
1076
01:10:08,290 --> 01:10:13,460
So the sum i equals
1 to n f of i
1077
01:10:13,460 --> 01:10:19,610
is upper bounded by that
guy, which is f of 1,
1078
01:10:19,610 --> 01:10:27,520
plus my integral, which is
the area under the curve.
1079
01:10:27,520 --> 01:10:31,400
The integral is the area under
that curve, starting here,
1080
01:10:31,400 --> 01:10:35,110
and that contains
all these rectangles,
1081
01:10:35,110 --> 01:10:38,126
and then I just add in f
of 1 to get an upper bound.
1082
01:10:41,540 --> 01:10:44,750
Now, for the lower bound,
think about shifting
1083
01:10:44,750 --> 01:10:47,830
the whole curve left by one.
1084
01:10:47,830 --> 01:10:51,190
That goes to there,
this goes to here,
1085
01:10:51,190 --> 01:10:56,740
that goes to here, that goes to
there, and that goes to there.
1086
01:10:56,740 --> 01:10:59,200
The area under the
curve did not change
1087
01:10:59,200 --> 01:11:02,710
when I shifted it left by one.
1088
01:11:02,710 --> 01:11:06,760
This is now my area
under the curve.
1089
01:11:06,760 --> 01:11:08,830
Stops here.
1090
01:11:08,830 --> 01:11:12,800
What do I get when I take that
area and add in this last box,
1091
01:11:12,800 --> 01:11:16,570
f of n?
1092
01:11:16,570 --> 01:11:19,699
A lower bound,
because it's contained
1093
01:11:19,699 --> 01:11:20,615
in all the rectangles.
1094
01:11:30,900 --> 01:11:36,492
Now, what's really weird
about these formulas,
1095
01:11:36,492 --> 01:11:37,408
do they look familiar?
1096
01:11:40,280 --> 01:11:41,780
Yeah.
1097
01:11:41,780 --> 01:11:43,300
Yeah.
1098
01:11:43,300 --> 01:11:44,961
I switched them.
1099
01:11:44,961 --> 01:11:45,460
Yeah.
1100
01:11:45,460 --> 01:11:48,870
They're the same formulas
we had over here,
1101
01:11:48,870 --> 01:11:51,730
except we switched the direction
on the less than and greater
1102
01:11:51,730 --> 01:11:53,970
than signs.
1103
01:11:53,970 --> 01:11:56,000
Well, I swapped f of 1
and f of n, however you
1104
01:11:56,000 --> 01:11:57,280
want to think about it.
1105
01:11:57,280 --> 01:12:00,570
The lower bound
here in that case
1106
01:12:00,570 --> 01:12:05,000
became the upper
bound in this case.
1107
01:12:05,000 --> 01:12:09,330
Is that possible that the lower
bound became the upper bound?
1108
01:12:09,330 --> 01:12:09,880
Yeah.
1109
01:12:09,880 --> 01:12:11,910
Yeah, because what
really happened here--
1110
01:12:11,910 --> 01:12:15,240
which is the big term
in this case, fn or f1?
1111
01:12:15,240 --> 01:12:17,290
f1 is the big term
because it's decreasing,
1112
01:12:17,290 --> 01:12:19,650
so it's totally symmetric.
1113
01:12:19,650 --> 01:12:20,680
All right?
1114
01:12:20,680 --> 01:12:22,970
The proof was very
similar, so the nice thing
1115
01:12:22,970 --> 01:12:25,710
is you've only got to remember
the bounds are now simple
1116
01:12:25,710 --> 01:12:28,730
for any sum as long as an
increasing or decreasing, it's
1117
01:12:28,730 --> 01:12:30,490
the same as the integral.
1118
01:12:30,490 --> 01:12:33,920
The lower bound is the smaller
of the first and last term,
1119
01:12:33,920 --> 01:12:36,650
and the upper bounds are larger
of the first and last term.
1120
01:12:36,650 --> 01:12:37,930
Very easy to remember.
1121
01:12:37,930 --> 01:12:39,554
Probably don't even
need the crib sheet
1122
01:12:39,554 --> 01:12:46,200
for it, although to be safe,
want to write that down.
1123
01:12:46,200 --> 01:12:50,060
So now it's easy to compute
good bounds on the sum
1124
01:12:50,060 --> 01:12:51,550
of the inverse square roots.
1125
01:13:02,020 --> 01:13:08,530
Any questions there
before I go do it?
1126
01:13:08,530 --> 01:13:11,440
So let's take the case
where we're summing 1
1127
01:13:11,440 --> 01:13:12,600
over square root of i.
1128
01:13:15,360 --> 01:13:22,970
So we compute the integral of
1 over square root of x dx.
1129
01:13:22,970 --> 01:13:29,500
That equals the square root of x
over 1/2, evaluated at n and 1.
1130
01:13:29,500 --> 01:13:33,650
That equals 2 square
root of n minus 1,
1131
01:13:33,650 --> 01:13:40,465
or two square root of n minus
2, and now we can bound the sum.
1132
01:13:48,650 --> 01:13:54,380
The upper bound is f
of 1 plus the integral.
1133
01:13:54,380 --> 01:13:58,975
The lower bound is f
of n plus the integral.
1134
01:14:02,420 --> 01:14:05,770
What is f of 1?
1135
01:14:05,770 --> 01:14:08,070
One?
1136
01:14:08,070 --> 01:14:09,530
One over the square
root of 1 is 1.
1137
01:14:09,530 --> 01:14:10,440
What is f of n?
1138
01:14:14,120 --> 01:14:15,400
One over the square root of n.
1139
01:14:15,400 --> 01:14:17,350
Small.
1140
01:14:17,350 --> 01:14:20,290
So these bounds are
pretty close here, right?
1141
01:14:20,290 --> 01:14:22,355
In fact, this gets really
tiny as n gets big,
1142
01:14:22,355 --> 01:14:23,730
so I'm just going
to replace this
1143
01:14:23,730 --> 01:14:26,570
with 2 square root of n minus
2 and make it a strict lower
1144
01:14:26,570 --> 01:14:30,185
bound, and this--
cancel there-- I
1145
01:14:30,185 --> 01:14:34,350
get 2 square root of n minus 1.
1146
01:14:34,350 --> 01:14:36,050
Wow, these bounds are great.
1147
01:14:36,050 --> 01:14:40,280
They're within one for all n.
1148
01:14:40,280 --> 01:14:43,260
That's really good.
1149
01:14:43,260 --> 01:14:48,570
So we can rewrite this in
terms of what really matters.
1150
01:14:48,570 --> 01:14:52,510
What really matters
in these bounds?
1151
01:14:52,510 --> 01:14:54,560
How fast is this
function growing?
1152
01:14:54,560 --> 01:14:55,420
AUDIENCE: 2 root n.
1153
01:14:55,420 --> 01:14:56,000
PROFESSOR: 2 root n.
1154
01:14:56,000 --> 01:14:58,208
That's what really matters,
so let's write that down.
1155
01:15:06,020 --> 01:15:09,506
So this says that the
sum i equals 1 to n
1156
01:15:09,506 --> 01:15:16,926
of 1 over square root i
equals 2 square root of n-- we
1157
01:15:16,926 --> 01:15:26,990
have a minus delta n, where
delta is between 1 and 2.
1158
01:15:26,990 --> 01:15:33,990
And so if I use the tilde
notation, what would I
1159
01:15:33,990 --> 01:15:36,210
write down here for the tilde?
1160
01:15:36,210 --> 01:15:39,054
Past the tilde?
1161
01:15:39,054 --> 01:15:39,970
I don't want to mess--
1162
01:15:39,970 --> 01:15:40,110
AUDIENCE: Tilde.
1163
01:15:40,110 --> 01:15:41,026
PROFESSOR: --I don't
want to keep track of all
1164
01:15:41,026 --> 01:15:42,599
the delta stuff as n gets big.
1165
01:15:42,599 --> 01:15:43,390
AUDIENCE: 2 root n.
1166
01:15:43,390 --> 01:15:48,420
PROFESSOR: 2 root
n, because this term
1167
01:15:48,420 --> 01:15:52,310
over that goes to 0 as
n gets large, so let's
1168
01:15:52,310 --> 01:15:53,090
just check that.
1169
01:15:56,630 --> 01:16:01,530
So we take the limit as n
goes to infinity of 2 root
1170
01:16:01,530 --> 01:16:06,235
n minus delta n over 2 root n.
1171
01:16:06,235 --> 01:16:08,150
I'm just checking
the definition now.
1172
01:16:08,150 --> 01:16:11,020
That's what the
definition would be.
1173
01:16:11,020 --> 01:16:17,380
Equals 1 minus the
limit as n goes
1174
01:16:17,380 --> 01:16:21,200
to infinity of 2 over 2 root n.
1175
01:16:21,200 --> 01:16:23,250
This is 0.
1176
01:16:23,250 --> 01:16:25,750
So it equals 1.
1177
01:16:25,750 --> 01:16:29,740
And so now you know that the
sum of the first n inverse
1178
01:16:29,740 --> 01:16:32,858
square roots grows as 2 root
n, which is the integral.
1179
01:16:32,858 --> 01:16:33,357
Yeah.
1180
01:16:33,357 --> 01:16:37,030
AUDIENCE: [INAUDIBLE] dropped
off the lower bound that f of n
1181
01:16:37,030 --> 01:16:38,610
was 1 over root n?
1182
01:16:38,610 --> 01:16:42,400
PROFESSOR: Yeah, I dropped it
off, because it was so tiny
1183
01:16:42,400 --> 01:16:45,150
and going to zero, I just
made a strict less than.
1184
01:16:45,150 --> 01:16:45,850
In fact, yes.
1185
01:16:45,850 --> 01:16:48,810
I don't hurt myself
by dropping it off.
1186
01:16:48,810 --> 01:16:51,040
In fact, the lower
bound was a little bit--
1187
01:16:51,040 --> 01:16:53,210
I made a little
weaker lower bound.
1188
01:16:53,210 --> 01:16:54,836
So this is still true.
1189
01:16:54,836 --> 01:16:56,710
I just-- it wasn't as
tight as it used to be,
1190
01:16:56,710 --> 01:16:59,474
so I could keep it around.
1191
01:16:59,474 --> 01:17:01,140
Yeah, it doesn't hurt
to keep it around,
1192
01:17:01,140 --> 01:17:04,280
then it's a less
than or equal there.
1193
01:17:04,280 --> 01:17:10,765
And now this would be
something like that.
1194
01:17:10,765 --> 01:17:13,140
So I could keep it around,
but I'm going to get rid of it
1195
01:17:13,140 --> 01:17:16,430
anyway, because I'm going
to go to the tilde notation,
1196
01:17:16,430 --> 01:17:19,877
and as n gets big,
this is really tiny.
1197
01:17:19,877 --> 01:17:21,460
So in this case, the
bounds are great.
1198
01:17:21,460 --> 01:17:26,540
You can nail it
pretty much right on.
1199
01:17:26,540 --> 01:17:27,290
Yeah.
1200
01:17:27,290 --> 01:17:30,290
AUDIENCE: You said one
over n still there,
1201
01:17:30,290 --> 01:17:32,290
the number is bigger than
it would normally be,
1202
01:17:32,290 --> 01:17:34,540
so when you take it
out, it becomes smaller,
1203
01:17:34,540 --> 01:17:38,635
so how could you go to
a less than [INAUDIBLE]?
1204
01:17:38,635 --> 01:17:40,510
PROFESSOR: Well, you're
saying you don't like
1205
01:17:40,510 --> 01:17:42,146
the fact I dropped it here?
1206
01:17:42,146 --> 01:17:42,729
AUDIENCE: Yes.
1207
01:17:42,729 --> 01:17:45,127
When you drop it, why do you
go to a less than instead of
1208
01:17:45,127 --> 01:17:45,627
[INAUDIBLE]?
1209
01:17:45,627 --> 01:17:51,610
PROFESSOR: Oh, because I've got
a bigger bound that I made less
1210
01:17:51,610 --> 01:17:52,480
when I dropped it.
1211
01:17:52,480 --> 01:17:55,550
I took something away, so I
know I could never equal this,
1212
01:17:55,550 --> 01:17:58,760
because I know it's
bigger than this.
1213
01:17:58,760 --> 01:18:01,710
I know that the real answer
has to be at least this big,
1214
01:18:01,710 --> 01:18:04,937
and so it has to be bigger
than something smaller.
1215
01:18:04,937 --> 01:18:05,770
That's why I did it.
1216
01:18:09,960 --> 01:18:13,240
Any other questions?
1217
01:18:13,240 --> 01:18:17,030
We'll get more practice tomorrow
and next time with this stuff.