A classic formula for estimating sums via integrals. Suppose \(f\) is a function defined on \([1, \infty)\) whose derivatives exist and are absolutely integrable. Then

\[ \begin{aligned} \color{blue}{ \sum_{1 \le k \le N} f(k) = \int_1^N f(x)\,dx + \frac{1}{2}f(N) + C_f + \frac{1}{12} f'(N) - \frac{1}{720}f^{(3)}(N) + \cdots } \qquad &\text{!} \\ \end{aligned} \]

Examples:

\[ \begin{aligned} H_N &= \int_1^N \frac{1}{x}\,dx + \frac{1}{2} \cdot \frac{1}{N} + \gamma - \frac{1}{12} \cdot \frac{1}{N^2} + O(\frac{1}{N^4}) \\ &= \ln{N} + \frac{1}{2N} + \gamma - \frac{1}{12N^2} + O(\frac{1}{N^4}) \\ \end{aligned} \]

\[ \begin{aligned} \ln{N!} &= \ln{N} + \ln{(N-1)} + \cdots \\ &= \int_1^N \ln{x}\,dx + \frac{1}{2} \ln{N} + \frac{1}{2} \ln{2\pi} + \frac{1}{12N} + O(\frac{1}{N^3}) \\ &= N\ln{N} - N + \ln{\sqrt{2\pi N}} + \frac{1}{12N} + O(\frac{1}{N^3}) & \text{Stirling's approximation} \\ &= (N + \frac{1}{2}) \ln{N} - N + \ln{\sqrt{2\pi}} + O(\frac{1}{N}) \\ \end{aligned} \]

Source: Analysis of Algorithm

# posted by rot13(Unafba Pune) @ 8:12 PM