1. ## Summation of 1/n

How do we prove that $\sum\limits_{n \leq x} \frac{1}{n} = \log{x} + C + O(\frac{1}{x})$.

2. Are you familiar with the Euler-MacLaurin formula or partial summation?

3. Let $S(x) = \sum_{n\leq x} 1 = \lfloor x \rfloor$.

By partial summation we get

$\sum_{n\leq x} \frac{1}{n} = \frac{S(x)}{x} + \int_{1}^{x} \frac{S(t)}{t^2} dt$.

$= \frac{\lfloor x \rfloor}{x} + \int_{1}^{x} \frac{\lfloor t \rfloor}{t^2} dt$.

$= 1-\frac{\{ x \} }{x} + \log(x) + \int_{1}^{x} \frac{\{ t \} }{t^2} dt$.

$= 1-\frac{\{ x \} }{x} + \log(x) + \int_{1}^{\infty} \frac{\{ t \} }{t^2} dt - \int_{x}^{\infty} \frac{\{ t \} }{t^2} dt$.

$= \log(x) + C + O\left(\frac{1}{x}\right) + O\left(\int_{x}^{\infty} \frac{1}{t^2} dt\right)$.

$= \log(x) + C +O\left(\frac{1}{x} \right)$.

Just to clarify, $C = 1+\int_{1}^{\infty} \frac{\{ t \} }{t^2} dt$

and $O\left(\frac{1}{x} \right) = -\frac{\{ x \} }{x}- \int_{x}^{\infty} \frac{\{ t \} }{t^2} dt$.

4. On a side note, this also proves $\int_{1}^{\infty} \frac{\{ t \} }{t^2} dt = 1-\gamma$.