asymptotics of sum

Question

I wanna find asymptotic of sum below $$\sum\limits_{k=1}^{[\sqrt{n}]}\frac{1}{k}(1 - \frac{1}{n})^k$$ assume I know asymptotic of this sum (I can be wrong): $$\sum\limits_{k=1}^{n}\frac{1}{k}(1 - \frac{1}{n^2})^k \sim c\ln{n}$$ So I use Stolz–Cesàro theorem and wanna show that $$\sum\limits_{k=1}^{[\sqrt{n}]}\frac{1}{k}(1 - \frac{1}{n})^k \sim c\ln{n}$$ where $$x_n = \sum\limits_{k=1}^{[\sqrt{n}]}\frac{1}{k}(1 - \frac{1}{n})^k$$ $$x_n - x_{n-1} = \frac{1}{\sqrt{n}}(1 - \frac{1}{n})^{\sqrt{n}}$$ $$y_n - y_{n-1} = \ln(n) - \ln(n-1)$$ but $$ \lim_{n \to \infty} \frac{\frac{1}{\sqrt{n}}(1 - \frac{1}{n})^{\sqrt{n}}} {\ln(n) - \ln(n-1)} = \infty $$ What I'm doing wrong?

Answer 1

One error that I see is your computation of $x_n-x_{n-1}$.

You have $x_n = \sum\limits_{k=1}^{[\sqrt{n}]}\frac{1}{k}(1 - \frac{1}{n})^k$.

Note that the individual terms depend on both $k$ and $n$.

Therefore,

$\begin{array}\\ x_n-x_{n-1} &=\sum\limits_{k=1}^{[\sqrt{n}]}\frac{1}{k}(1 - \frac{1}{n})^k -\sum\limits_{k=1}^{[\sqrt{n-1}]}\frac{1}{k}(1 - \frac{1}{n-1})^k\\ &=\sum\limits_{k=1}^{[\sqrt{n-1}]}\left(\frac{1}{k}(1 - \frac{1}{n})^k -\frac{1}{k}(1 - \frac{1}{n-1})^k\right) +\frac{[\sqrt{n}]-[\sqrt{n-1}]}{[\sqrt{n}]}(1 - \frac{1}{n})^{[\sqrt{n}]}\\ &=\sum\limits_{k=1}^{[\sqrt{n-1}]}\frac{1}{k}\left((1 - \frac{1}{n})^k -(1 - \frac{1}{n-1})^k\right) +\frac{[\sqrt{n}]-[\sqrt{n-1}]}{[\sqrt{n}]}(1 - \frac{1}{n})^{[\sqrt{n}]}\\ \end{array} $

which is (unfortunately) a lot more complicated.

You can work with $(1 - \frac{1}{n})^k -(1 - \frac{1}{n-1})^k $, but that sum will still remain.

(added later)

Since $k < \sqrt{n}$, $\frac{k}{n} =O(\frac{1}{\sqrt{n}}) $ and $\frac{k^2}{n^2} =O(\frac{1}{n}) $, so $(1 - \frac{1}{n})^k =1-\frac{k}{n}+\frac{k(k-1)}{2n^2}+O(\frac{k^3}{n^3}) =1-\frac{k}{n}+\frac{k(k-1)}{2n^2}+O(\frac{1}{n^{3/2}}) $.

Therefore

$\begin{array}\\ (1 - \frac{1}{n-1})^k-(1 - \frac{1}{n-1})^k &=(1-\frac{k}{n-1}+\frac{k(k-1)}{2(n-1)^2}+O(\frac1{n^{3/2}})) -(1-\frac{k}{n}+\frac{k(k-1)}{2n^2}+O(\frac1{n^{3/2}}))\\ &=(\frac{k}{n}-\frac{k}{n-1}) -(\frac{k(k-1)}{2(n-1)^2}-\frac{k(k-1)}{2n^2})+O(\frac1{n^{3/2}}))\\ &=-\frac{k}{n(n-1)} -\frac{k(k-1)}{2}(\frac1{(n-1)^2}-\frac1{n^2}) +O(\frac1{n^{3/2}}))\\ &=-\frac{k}{n(n-1)} -\frac{k(k-1)}{2}(\frac{2n-1}{n^2(n-1)^2}) +O(\frac1{n^{3/2}}))\\ \end{array} $

If we sum this we get

$\begin{array}\\ \sum\limits_{k=1}^{[\sqrt{n-1}]}\frac{1}{k}\left((1 - \frac{1}{n})^k -(1 - \frac{1}{n-1})^k\right) &=\sum\limits_{k=1}^{[\sqrt{n-1}]}\frac{1}{k} \left(-\frac{k}{n(n-1)} -\frac{k(k-1)}{2}(\frac{2n-1}{n^2(n-1)^2}) +O(\frac1{n^{3/2}}))\right)\\ &=-\sum\limits_{k=1}^{[\sqrt{n-1}]}\frac{1}{n(n-1)} -\sum\limits_{k=1}^{[\sqrt{n-1}]} \frac{k-1}{2}(\frac{2n-1}{n^2(n-1)^2}) +O(\frac1{n})\\ &=-\frac{[\sqrt{n-1}]}{n(n-1)} -\frac{[\sqrt{n-1}]([\sqrt{n-1}]-1}{2}(\frac{2n-1}{n^2(n-1)^2}) +O(\frac1{n})\\ &=O(\frac1{n^{3/2}}) +O(\frac1{n^{2}}) +O(\frac1{n})\\ \end{array} $

At this point, that $O(1/n)$ dominates, so another term should be taken in the expansion of $(1 - \frac{1}{n})^k$ to get a more accurate estimate for $x_n-x_{n-1}$.

But this was such a pain that I am going to leave it at this.

Answer 2

Another method you could try is rewriting your sum as

$$ \sum_{k=1}^{\lfloor\sqrt{n}\rfloor} \frac{1}{k} - \sum_{k=1}^{\lfloor\sqrt{n}\rfloor} \frac{1}{k} \left[1-\left(1-\frac{1}{n}\right)^k\right], $$

then using Bernoulli's inequality to show that the second sum is $O(n^{-1/2})$.