asymptotics of sum 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?
 A: 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})$.
A: 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.
