PROFESSOR: So we figured out that you
can get the book stack, the overhang of the books,
to be half the harmonic sum.
With n books, you can get out Hn over 2
where Hn is this harmonic sum, or harmonic number.
The question is, how are we going to estimate or calculate
what this sum is?
Now it turns out there is no simple formula for exactly
what this sum is, but there is a simple formula that
estimates it quite accurately.
And we get the estimation by bounding the sum by integrals.
And so let's look at this integral method for estimating
sums.
Remember what I wanted was the sum of 1 plus 1/2
plus 1/3 down to 1 over n.
So let's form some unit width rectangles of heights
equal to the amount that I want.
So here's a rectangle of height 1, rectangle of height 1/2,
rectangle of height 1/3.
I'm going out here, if you actually count to 8,
but let's propose that this is a height 1 over n.
And what I know is that the total area of these rectangles
is actually equal to the number that I want.
The total area of these rectangles
is the harmonic number.
And I'm interested in a lower bound for Hn, because I want
to know how far I can get out.
I want a tight lower bound.
It says Hn is larger than a certain amount.
That's the amount that I'm sure that I can stack out in books.
So the way I'm going to get a lower bound on this number Hn
is by looking at this curve that goes
through the corners of the rectangles.
And if you check it, that curve is 1 over x plus 1.
That is, the point here is-- when x is 0, I'm at 1 over 1.
When x is 1, I'm at 1/2, the height of the second rectangle,
and so on.
So 1 over x plus 1 is a curve that
is strictly below the boundaries of all these rectangles.
That means that the area under 1 over x plus 1 going from 0 to n
is a lower bound on Hn, because it's a lower bound
on the area of the rectangles.
So Hn equals the area of the rectangles.
It's greater than the area of 1 over x plus 1,
which of course is equal to the integral from 0
to n of 1 over x plus 1, which shifting variables is
the same as the integral from 1 to n plus 1 of 1 over x
dx, which of course we know is a natural logarithm of n plus 1.
So there we have it.
The overhang that you need for three books, which
is Bn greater than or equal to 3,
means that Hn has to be greater than or equal to 6.
So by this estimate, I need log of n
plus 1 greater than or equal to 6
in order to get three books out, that the back end
of the top book is two books past the edge of the table
and the right end of the furthest out book
is three book lengths past the edge of the table.
So my bound tells me that I need n books such
that log of n plus 1 is greater than or equal to 6.
Well, exponentiating both sides, the right-hand side
becomes e to the 6th.
And I figure out that as long as n
is greater than or equal to e to the 6th minus 1 books-- rounded
up, of course, because there's only-- you can't have fractions
of a book-- you get an estimate that with 403 books,
I can actually get my stack to stick out three book lengths
past the edge of the table.
Well if you do the actual calculation
instead of the estimate, it turns out
that 227 books are enough.
So this estimate's a little off.
But for our purposes, it tells us
a dramatic fact, which is that we know that log of n plus 1
approaches infinity as n approaches infinity.
And that means that, with enough books,
I can get out as far as I want.
You tell me how many book lengths you want to be out,
I'll use the log n formula to calculate how many books I
need to get that far out.
So here's an example of some students in the class
some years ago decided to do this as an experiment.
Now when we used to do this in class,
we first tried to do it with the big, heavy textbook
that we used.
And we kept trying to get them to balance and go out
over the edge of the table, and they
failed, because it turns out that textbooks are heavy
and they compress.
They're not the rigid rectangular cross sections
that our model was based on.
But CD cases work very well.
They are more rigid.
They don't compress easily, and they're very lightweight
so that they don't cause problems
with distortions because of the size of the stack.
And so you can actually get CD cases to stick out pretty far.
This is an example where it's 43 CD cases high,
and the top four cases are completely
past the edge of the table.
The leftmost edge is about 1.81 or 1.91 case lengths
past the table.
There's another view of it from the guy who made the stack.
And of course, they were right on the edge of stability
in trying to get the CDs to stick out as far as possible.
So if you notice these little spaces there,
in terms of the balancing, it's really just
on the brink of falling over.
If you sneeze at it, it'll tip.
But if you don't sneeze at it, it's stable,
and you get the top CD out that far.
So while we're at it, let's get an upper bound for Hn.
We just got a lower bound of Hn, but the same kind
of logic of using an integral will give you
an upper bound for Hn.
What I do now is I run a curve from the upper right
corners of the rectangles.
And that curve is simply 1 over x.
So an upper bound for the harmonic number
Hn is the area under 1 over x out to n plus this 1.
And so I get an upper bound that says that the harmonic number
Hn is less than the integral from 1
to n of 1 over x dx plus 1, or it's equal to 1 plus log of n.
So combining those two bounds that I
got by looking at a curve that's a lower bound on the area
and a curve that's an upper bound on the area
and integrating, I discover that Hn is bracketed
between the natural log of n plus 1 and 1
plus the natural log of n.
Now these two numbers, log of n plus 1 and 1 plus log of n,
are very close, and they get closer and closer as n grows.
So it turns out that what we can say pretty accurately
is that Hn is asymptotically equal to log n.
It's approximately equal to log n.
And the precise definition of this tilde symbol
that I've highlighted in magenta is called asymptotically equal.
And the general definition of asymptotically equal,
that Hn is asymptotically equal to log n,
is that a function f of n is asymptotically
equal to a function g of n when the limit of their quotient
goes to 1.
That is to say, as a multiplicative factor,
each is within a constant one of the other in the limit.
1 plus epsilon of-- 1 plus or minus epsilon of gn
is going to bracket fn, and vice versa.
Asymptotic equivalents, or asymptotic equality.
Let's do an example.
So the remark would be, for example,
that n squared plus n is asymptotically
equal to n squared.
Why?
Well let's look at the limit as n approaches infinity of n
squared plus n over n squared.
It's the same as simplifying algebraically
the limit of 1 over 1 plus n.
As n approaches infinity, that term goes to zero.
Sure enough, the limit is 1, and so these two terms
are asymptotically equal.
The idea of asymptotically equal is that all we care about
is the high order term.
The low order terms will disappear,
and we're looking at the principal term that
controls the growth rate of the functions when we look at them
up to asymptotic equivalence.
So let's step back for just a moment
and generalize what we've done here
with estimating the harmonic sum.
There's a general method called the integral method where,
in this particular case, suppose we
have a function f, the positive real valued function
that's weakly decreasing, like 1 over x.
Then let's let S be the sum from i equals 1 to n of f of i.
So I was interested where f of x was 1 over x,
and I wanted the sum from 1 over-- 1 to n of 1
over i, which was the nth harmonic number.
And I was comparing that to the integral from 1 to n
of f of x, or 1 over x in our example.
So if I is the integral and S is the sum that I want,
what we can conclude really is that, in general, the sum
is bracketed between the integral plus the first term
of f of 1 in the sum, and the integral plus
the last term of the sum.
Remember, f is weakly decreasing, so f of n
is smaller than f of 1.
There's a similar theorem actually, just reverse f of 1
and f of n, to use an integral estimate
to get a bound on a weakly increasing function.
And that gives us a general tool for estimating
the growth rate of sums.