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

Answer by Eugene Yarovoi:

So far the answers here have used calculus. However, you asked for an "intuitive" explanation, and it is likely that calculus is not intuitive to you, much less the evaluation of that particular integral.
I will give a very elementary argument for why [math]\sum_{k=1}^n \frac {1}{k} = \Theta (\log n)[/math].
Consider the following: [math]1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + … + 1/n \leq 1 + 1/2 + 1/2 + 1/4 + 1/4 + 1/4 + 1/4 + …+ 1/n =[/math][math]1 + 2 \times 1/2 + 4 \times 1/4 + … + n \times 1/n[/math]. It takes [math]\log_2 n [/math] multiplies by 2 to reach n, and each summand in the final sequence equals 1.
So, [math]\sum_{k=1}^n \frac {1}{k} \leq \lceil \log_2 n \rceil + 1 [/math].
We can also obtain a lower bound by rounding to powers of two in a different direction:
[math]1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + … + 1/n [/math][math]\geq 1 + 1/2 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + …+ 1/n.[/math] Here each group of identical powers of two is worth 1/2, and then there's the 1. So here we get [math]1 + \frac {1}{2} \lfloor \log_2 n \rfloor[/math].
Therefore, the sum is [math]\Theta (\log n)[/math].

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