Approximating the sum of integers with the logarithm

Question

Why does the following hold?

$\sum_{j=1}^{n-1}j \to \log(n) \text{ as } n \to \infty$

Thanks!

Answer 1

Well it's true in the sense that they both approach infinity as $n\rightarrow\infty$ however

$$\sum_{i=1}^n i = \frac{n(n+1)}{2}.$$

The (natural) logarithm does not behave polynomially at all $-$ in fact it grows slower than $x^{\alpha}$ for any $\alpha>0$. The sum is polynomial in $n$ so I'm not sure what you've stated is actually true in any meaningful way.

To see that $\log(x)$ grows slower than any $x^{\alpha}$ where $\alpha > 0$, a simple application of L'Hospital's rule is prudent:

$$\begin{align}\lim_{x\rightarrow\infty}\frac{x^{\alpha}}{\log(x)} &= \frac{\infty}{\infty} \\ &= \lim_{x\rightarrow\infty} \frac{\alpha x^{\alpha-1}}{\frac{1}{x}} \\ &= \lim_{x\rightarrow\infty} \alpha x^{\alpha} \\ &=\infty\end{align}.$$

Alternatively, you can see this by noting that $e^x$ grows faster than any (positive) power of $x$.

Answer 2

As stated, the sum of integers up to $n$ is not well approximated by the logarithm of $n$. However the sum of inverse integers $\sum_{k=1}^n 1/k$ does grow just like the natural logarithm $\log n$, and in fact the difference $\log n - \sum_{k=1}^n 1/k$ tends to a constant called the Euler constant. This is much stronger than saying that the ratio goes to $1$.