8
$\begingroup$

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}.$$

$\endgroup$
6
$\begingroup$

$$\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$.

$\endgroup$
  • 1
    $\begingroup$ (+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 ;) $\endgroup$ – Jack D'Aurizio Jan 24 '15 at 16:33
  • 1
    $\begingroup$ @JackD'Aurizio: perhaps, but still, I still like to understand the error involved as I take the limit. $\endgroup$ – Ron Gordon Jan 24 '15 at 16:53
  • $\begingroup$ Perfectly fine. $\endgroup$ – Jack D'Aurizio Jan 24 '15 at 16:59
4
$\begingroup$

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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.