# Does $n\log(n)$ diverge or converge from this sum of quotients?

By playing with numbers, I discovered that

$n\ln(n) \approx \sum_{k=1}^n{\frac{n}{k}}$

And for $n = 1,2,...20,000$ the two quantities are almost neck-and-neck.

It reminds me of the Stirling approximation. Does anyone know if this approximation has a name?

They may even converge... this is the ratio of the sum / log as a function of n:

I forgot the calculus tests for divergence/convergence, so an example proving divergence would be great.

• Note that $\sum_{i=k}^n n/k = n \sum_{i=1}^n 1/k$ and using the approximation $\sum_{k=1}^n f(k) \approx \int_1^n f(k) dk$ you get (more or less) your approximation. Jan 18, 2017 at 8:22
• $\lim_{m\to\infty}\left(\sum_1^m(1/k)-\log m\right)$ exists and is about $0.57721$ – it's called the Euler-Mascheroni constant, $\gamma$. Jan 18, 2017 at 8:26
• By graphing $1/x$ you can convince yourself that : $$\int_1^{n+1} 1/x\ dx\ \leq\ \sum_{i=1}^n 1/i\ \leq\ 1 + \int_1^n 1/x\ dx$$ Therefore : $$\ln(n+1)\ \leq\ \sum_{i=1}^n 1/i\ \leq\ 1 + \ln(n)$$ Jan 18, 2017 at 8:39

Expanding my comments : Note that your claim $n\cdot \ln(n) \approx \sum_{i=1}^n \frac{n}{i}$ is equivalent to say $\ln(n) \approx \sum_{i=1}^n \frac{1}{i}$ simply by dividing both sides of the equality by $n$.
Now let us analyze the approximation $\ln(n) \approx \sum_{i=1}^n \frac{1}{i}$ :
By graphing $y = 1/x$ and noting that the summation can be thought as summing the areas of rectangles of base-length $1$ and height $1/x$ we can conclude that $$\int_1^{n+1} \frac{1}{x}\ dx\ \leq\ \sum_{i=1}^n \frac{1}{i}\ \leq\ 1 + \int_1^n \frac{1}{x}\ dx$$ Computing the integral gives us : $$\ln(n+1)\ \leq\ \sum_{i=1}^n \frac{1}{i}\ \leq\ 1 + \ln(n)$$
Now let's analyse the absolute difference between the two sides of the approximation. Namely : $\sum_{i=1}^n \frac{1}{i} - \ln(n)$. From our inequalities we get : $$\ln(n+1)- \ln(n) \ \leq\ \sum_{i=1}^n \frac{1}{i} -\ln(n)\ \leq\ 1$$ Writing $\ln(n+1)- \ln(n) = \ln(\frac{n+1}{n}) = \ln(1+1/n)$ we get that : $$\ln(1+ 1/n) \ \leq\ \sum_{i=1}^n \frac{1}{i} -\ln(n)\ \leq\ 1$$ Applying $\lim_{n \rightarrow \infty}$ we see that the absolute difference is clearly bounded. (This doesn't prove the convergence but gives an intuition. Note that it acctually converges to $\gamma$) $$0 \ \leq\ \lim_{n \rightarrow \infty} \sum_{i=1}^n \left( \frac{1}{i} -\ln(n)\right) \ \leq\ 1$$ Now analyzing the relative difference $\frac{\sum_{i=1}^n \frac{1}{i}}{\ln(n)}$, starting again from our inequalities : $$\frac{\ln(n+1)}{\ln(n)}\ \leq\ \frac{\sum_{i=1}^n \frac{1}{i}}{\ln(n)}\ \leq\ \frac{1 + \ln(n)}{\ln(n)}$$ $$\frac{\ln(n+1)}{\ln(n)}\ \leq\ \frac{\sum_{i=1}^n \frac{1}{i}}{\ln(n)}\ \leq\ 1+\frac{1}{\ln(n)}$$ Applying again $\lim_{n \rightarrow \infty}$ (and modulo some limits caclulations) we get $$1\leq\ \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1}{i}}{\ln(n)} \leq 1$$ and the sandwich theorem let us conclude that the relative difference goes indeed to $1$.