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?

### Like this:

Like Loading...

*Related*