Harmonic Series Approximation

$$H(n) = 1+1/2+1/3+...1/n$$ This is Area under the curve $\int_1^n 1/x dx $ is $log n - log 1$ (this is an approximation) $$log n - 0$$ $$log n$$ Refer to youtube http://www.youtube.com/watch?v=H5PcgX6i0wY CLRS also has a proof: see apendix A For a monotonically decreasing function $$\int_m^{n+1} f(x) dx \leq \sum\limits_{k=1}^n f(k) \leq \int_{m-1}^n f(x) dx $$ for the lower bound $$\int_m^{n+1} 1/x dx \leq \sum\limits_{k=1}^n 1/k $$ $$ log(n+1) - log 1 \leq \sum\limits_{k=1}^n 1/k $$ $$ log(n+1) \leq \sum\limits_{k=1}^n 1/k $$ for upper bound $$\sum\limits_{k=2}^n 1/k \leq \int_{1}^n 1/n dx $$ $$\sum\limits_{k=2}^n 1/k \leq log n - log 1 $$ $$\sum\limits_{k=2}^n 1/k \leq log n $$