Proving harmonic series is bounded by log n
divcurl
you could group the terms of the harmonic series, such that
you get the following result:
1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + ...
transforms into:
1 + (1/2) + (1/2 + 1/2) + (1/2 + 1/2 + 1/2 + 1/2) + ...
so say you have k groups which give rise to 2^k terms
hence, 2^k = n <=> k = log_2(n)
What's another way of showing this? I suppose
one could also use the limit comparison test but
any other interesting ways?
Joshua Cranmer
The way I was taught was to use a modified argument of the integral test
to show that ln(k) < sum of k harmonic numbers < ln(k + 1).
--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
Gerry
> On 09/04/2010 03:45 PM, divcurl wrote:
>
> > To show the harmonic series is bounded by BigTheta(log n)
> > you could group the terms of the harmonic series, such that
> > you get the following result:
> > 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + ...
> > transforms into:
> > 1 + (1/2) + (1/2 + 1/2) + (1/2 + 1/2 + 1/2 + 1/2) + ...
> > so say you have k groups which give rise to 2^k terms
> > hence, 2^k = n<=> k = log_2(n)
>
> > What's another way of showing this? I suppose
> > one could also use the limit comparison test but
> > any other interesting ways?
>
> The way I was taught was to use a modified argument of the integral test
> to show that ln(k) < sum of k harmonic numbers < ln(k + 1).
Shouldn't that log(k + 1) be (log k) + 1?
After all, the limit of (sum to n) minus (log n) is gamma,
Euler's constant, which is about .577.
--
GM
W^3
<7aa17d51-bec2-4b29...@p37g2000pra.googlegroups.com>,
Gerry <ge...@math.mq.edu.au> wrote:
No, forget about the fancy stuff and just look at the picture.
Ray Vickson
Let int(f(x), x=a..b) stand for integral{f(x) dx, x = a to b}. We have
1/2 < int(1/x, x=1..2), 1/3 < int(1/x, x=2..3), ... 1/n < int(1/x,
x=(n-1)..n), so 1/2 + 1/3 + ... + 1/n < int(1/x, x=1..n) = ln(n).
Thus, 1 + 1/2 + ... + 1/n < 2*ln(n) = 2*ln(2)*log_2(n).
R.G. Vickson
Gerry
> In article
> <7aa17d51-bec2-4b29-bc0e-17ba14e07...@p37g2000pra.googlegroups.com>,
Forget about the picture, and look at k = 1.
The sum of 1 harmonic number is 1.
log(1 + 1) = .69....
"sum of k harmonic numbers < log(k + 1)" is clearly false
for k = 1 (and, I imagine, for every k).
If your picture tells you something different,
it's time to draw a better picture.
--
GM
David C. Ullrich
wrote:
Just to wrap this up for readers other than you and W who
are wondering:
Of course the problem is at the left edge of the picture:
It's clear from just looking that 1 + ... + 1/k is no
larger than int_0^k 1/t dt, but that estimate is a
little too loose to be very useful.
So one simply lets the first term sit there and
applies an integral test to the sum 1/2 + ... + 1/k,
and sure enough the original sum turns out to
be <= log(k) + 1.
W^3
<23d058ee-802f-4de8...@q16g2000prf.googlegroups.com>,
Gerry <ge...@math.mq.edu.au> wrote:
Yes, you're right. Somehow I got the above confused with int_1^n ln(x)
dx < sum_{k=1}^n ln(k) < int_1^(n+1) ln(x) dx.
Dave L. Renfro
Others have already responded. I'm only jumping in because
your question reminded me of a question I asked a while back
(March 2001) in sci.math and which several people (especially
David Petry, David C. Ullrich, Robin Chapman, and Peter
L. Montgomery) were able to help me with:
sci.math thread: Help with 1/2 - (1/8)*x < 1/x - 1/(e^x - 1)
18-22 March 2001
http://tinyurl.com/2b3x7qt
In the last post of that thread I mention your method of grouping,
which incidentally can be done in such a way to obtain fairly
tight upper and lower bounds for the sum, and thus the method
can be used to obtain good estimates for the sum of the first
10^20, 10^100, etc. terms using nothing more than precalculus
level math.
Back in March 2001 I was interviewing for a math position
(at Southern Oregon University, if anyone's interested)
and decided to change my 60 min "interview talk" at the
"last minute". (I realized that what I originally planned
to talk about was going to be too unfocused, and it was
also not really all that relevant for someone being hired,
in part, to teach undergraduate real analysis.) I decided
that a hand-out I'd written a few years before, when I was
teaching at a high school "math/science academy", would work
perfectly (and it did, although I didn't get the job), but
when I was going over it I realized that I didn't know (or
had forgotten) how to do a step that I had left for my
students to do, and sent out a call for help in sci.math.
The handout itself is posted at the URL below, under
the name "Euler-const.pdf". The handout is essentially
unchanged from the original January 1999 version (which
itself is based on an older handwritten handout I used
at that high school, before I finally got around to
preparing a typed version), with the exception of a few
references added at the end and a footnote on p. 5 that
incorporates some of the comments I got in that sci.math
thread from 2001. Incidentally, the "precalculus method"
for estimating the partial sums of the harmonic series is
not discussed in this handout, but I included it in the
early part of my talk. I used it to indicate how one can
"do mathematics" -- someone comes up with the grouping
proof for divergence, then someone else (or the same person)
picks apart the grouping proof and notices that we can
get upper and lower bounds for the rate of divergence
from the grouping proof . . .
http://mathforum.org/kb/message.jspa?messageID=6544585
Dave L. Renfro