What is an intuitive way to see why harmonic series sums to logn?

Answer by Daniel Merthe:

Mark's answer is good. But you asked for a way to "see" why
[math]\sum_{k=1}^{n} \frac{1}{k} \sim \log{n}[/math]
Below I have plotted the function [math]f(x) =1/x[/math] in red along with a series of rectangles, each one corresponding to a term in the sum. The first big rectangle on the left corresponds to the [math]k=1[/math] term with an area of 1, the second smaller rectangle corresponds to the [math]k=2[/math] term with an area of 1/2, and so on. You can see that the rectangles of increasing [math]k[/math] get closer and closer to the curve [math]f(x) =1/x[/math].
Now, the sum is just the total area of all of the [math]n[/math] rectangles. If [math]n[/math] is very large, then this area is approximately equal to the area under the red curve from [math]x=1[/math] to [math]x=n[/math]. But the area under the curve is just the integral of [math]f(x),[/math]
[math]\int_1^n f(x) dx = [/math][math]\int_1^n \frac{dx}{x} = \log{n} [/math]
Moreover, as [math]n[/math] increases this approximation gets better, because the rectangles and the curve get closer as [math]k[/math] increases. So, we say that the two areas are asymptotically equal as [math]n[/math] goes to infinity.

What is an intuitive way to see why harmonic series sums to logn?

Advertisements

Leave a comment

Filed under Life

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s