# Compute the limit $\lim_{n\to\infty}\frac{1}{\log n}\sum_{k=1}^n\left(1-\frac{1}{n}\right)^k\frac{1}{k}$

Similar to this problem, how can one compute the following limit: $$\lim_{n\to\infty}\frac{1}{\log n}\sum_{k=1}^n\left(1-\frac{1}{n}\right)^k\frac{1}{k}\quad ?$$

Note that $$\log x = \sum_{k=1}^{\infty}\left(1-\frac{1}{x}\right)^k\frac{1}{k},\quad x\ge \frac{1}{2}.$$

$$\left ( 1-\frac1{n}\right )^k = e^{k \log{(1-1/n)}} = e^{-k/n + O(1/n^2)} = 1-\frac{k}{n}+O \left ( \frac1{n^2} \right )$$

So as $n \to \infty$,

\begin{align}\frac1{\log{n}} \sum_{k=1}^n \left ( 1-\frac1{n}\right )^k \frac1{k} &= \frac1{\log{n}} \sum_{k=1}^n \left (\frac1{k}- \frac1{n} + O \left ( \frac1{n^2} \right ) \right ) \\ &= \frac{H_n - 1}{\log{n}} + O \left ( \frac1{n \log{n}} \right ) \\ &= 1 - \frac{1-\gamma}{\log{n}} + O \left ( \frac1{n \log{n}} \right ) \end{align}

The limit as $n \to \infty$ is thus $1$.

• (+1) As a matter of fact, we both over-killed the problem since the inequality $$1-\frac{k}{n}\leq\left(1-\frac{1}{n}\right)^k\leq 1$$ was enough ;) – Jack D'Aurizio Jan 24 '15 at 16:33
• @JackD'Aurizio: perhaps, but still, I still like to understand the error involved as I take the limit. – Ron Gordon Jan 24 '15 at 16:53
• Perfectly fine. – Jack D'Aurizio Jan 24 '15 at 16:59

Since: $$\left(1-\frac{1}{n}\right)^{k}\frac{1}{k}=\int_{0}^{1-1/n}x^{k-1}\,dx=\frac{1}{k}-\int_{0}^{\frac{1}{n}}(1-x)^{k-1}\,dx$$ we have:

$$\sum_{k=1}^{n}\left(1-\frac{1}{n}\right)^{k}\frac{1}{k}=H_n-\int_{0}^{\frac{1}{n}}\frac{1-(1-x)^n}{x}\,dx,\tag{1}$$ but since $f_n(x)=\frac{1-(1-x)^n}{x}$ is a positive decreasing function on the interval $\left(0,\frac{1}{n}\right)$ and $\lim_{x\to 0^+}f_n(x) = n$, we have: $$0\leq \int_{0}^{\frac{1}{n}}f_n(x)\,dx \leq \int_{0}^{\frac{1}{n}}n\,dx = 1,\tag{2}$$ so the initial limit equals: $$\lim_{n\to +\infty}\frac{H_n}{\log n}=\color{red}{1}.\tag{3}$$