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?


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


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


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


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


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.