Asymptotics of $e^{-n}\sum_{k=0}^{n-1}\frac{n^k}{k!}\cdot\frac1{n-k}$

Here we follow exercise 5.2 from Asymptopia by Joel Spencer and show OP's assumption is correct.

The following is valid \begin{align*} \color{blue}{\sum_{k=1}^n\frac{n^{\underline{k}}}{n^k}\cdot\frac{1}{k}\sim \frac{1}{2}\ln n} \end{align*}

where $n^{\underline{k}}=n(n-1)\cdots(n-k+1)$ denotes the falling factorial.

A convenient approach is to split the index range of $k$ into three parts:

• a small range: $\qquad\quad k<\frac{\sqrt{n}}{\ln n}$

• a middle range: $\quad\quad \frac{\sqrt{n}}{\ln n} < k < \sqrt{n}\ln n$

• and a large range: $\ \quad k>\sqrt{n}\ln n$.

Small range: $k<\frac{\sqrt{n}}{\ln n}$

We write \begin{align*} \frac{n^{\underline{k}}}{n^k}=\prod_{j=1}^{k-1}\left(1-\frac{j}{n}\right) \end{align*} and consider the logarithm of the product. Since $$\ln(1-x)=-x+O(x^2)$$ when $x\rightarrow 0$ we obtain \begin{align*} \ln\left(\frac{n^{\underline{k}}}{n^k}\right)&=\sum_{j=1}^{k-1}\ln\left(1-\frac{j}{n}\right)\\ &\sim\sum_{j=1}^{k-1}-\frac{j}{n}\sim -\frac{k^2}{2n}=o(1) \end{align*} Thus we have \begin{align*} \frac{n^{\underline{k}}}{n^k}\sim 1\tag{1} \end{align*} We obtain from (1) \begin{align*} \color{blue}{\sum_{k}\frac{n^{\underline{k}}}{n^k}\cdot\frac{1}{k}}&\sim\sum_{k}\frac{1}{k}\sim\ln\left(\frac{\sqrt{n}}{\ln n}\right)\\ &\sim\ln\sqrt{n}-\ln\ln n\\ &\,\,\color{blue}{\sim\frac{1}{2}\ln n}\tag{2} \end{align*}

Medium range: $\frac{\sqrt{n}}{\ln n}<k<\sqrt{n}\ln n$

Since $\frac{n^{\underline{k}}}{n^k}\leq 1$ we obtain \begin{align*} \color{blue}{\sum_{k}\frac{n^{\underline{k}}}{n^k}\cdot\frac{1}{k}}&\leq \sum_{k}\frac{1}{k}\\ &\sim\ln\left(\sqrt{n}\ln n\right)-\ln\left(\frac{\sqrt{n}}{\ln n}\right)\\ &\sim \ln \sqrt{n}+\ln\ln n-\ln \sqrt{n}+\ln \ln n\\ &\,\,\color{blue}{\sim{2\ln \ln n}}\tag{3} \end{align*}

Large range: $k>\sqrt{n}\ln n$

Here we have $\frac{n^{\underline{k}}}{n^k}=o(1)$ and we obtain \begin{align*} \color{blue}{\sum_{k}\frac{n^{\underline{k}}}{n^k}\cdot\frac{1}{k}}&=o(1)\sum_{k}\frac{1}{k}\\ &= o(1)\left(\ln n-\ln \left(\sqrt{n}\ln n\right)\right)\\ &\,\,\color{blue}{=o(\ln n)}\tag{4} \end{align*}

We see (2) provides the main contribution compared with (3) and (4) and the claim follows.