During calculations of an expectation of some random variable, I have encountered the following sum:
\begin{equation} \sum_{t=2}^{n+1} \frac{t(t-1) \cdot n!}{(n-t+1)!\cdot n^t} \end{equation}
I was trying to get an asymptotic approximation for this expression. Plotting it for $n$ which are up to 140, it looked a little bit like some power of $n$, perhaps somewhere between 0.5 and 1. I have tried applying Stirling's approximation to the factorials, but that didn't make things easier.
Here's my plot:
Any ideas?
Add the $t=1$ term since it is $0$ and use the change of variable $t=n+1-s$, then $t(t-1)=n(n+1)-2ns+s(s-1)$ hence the $n$th sum is $$ S_n=\sum_{s=0}^n\frac{n(n+1)-2ns+s(s-1)}{s!}\,\frac{n!}{n^{n+1-s}}, $$ that is, $$ S_n=\left((n+1)U_n-2V_n+\frac1nW_n\right)\,\frac{n!}{n^{n}}, $$ where $$ U_n=\sum_{s=0}^n\frac{n^s}{s!},\quad V_n=\sum_{s=0}^n\frac{sn^s}{s!},\quad W_n=\sum_{s=0}^n\frac{s(s-1)n^s}{s!}. $$ Thus, $$ V_n=n\sum_{s=0}^{n-1}\frac{n^s}{s!}=nU_n-\frac{n^{n+1}}{n!}=nU_n-n\frac{n^{n}}{n!}, $$ and $$ W_n=n^2\sum_{s=0}^{n-2}\frac{n^s}{s!}=n^2U_n-\frac{n^{n+2}}{n!}-\frac{n^{n+1}}{(n-1)!}=n^2U_n-2n^2\frac{n^{n}}{n!}. $$ Putting these together and watching with delight the cancellations occur yields $$ S_n=U_n\,\frac{n!}{n^{n}}. $$ A nice probabilitic argument to estimate $U_n$ is to note that $$ \mathrm e^{-n}\,U_n=P(X_n\leqslant n), $$ where $X_n$ is a Poisson random variable with parameter $n$, thus the central limit theorem shows that $$ \mathrm e^{-n}\,U_n\to\frac12. $$ Stirling's formula (finally) shows that $$ \mathrm e^{n}\,\frac{n!}{n^{n}}\sim\sqrt{2\pi n}, $$ hence $$ \lim_{n\to\infty}\frac{S_n}{\sqrt{n}}=\sqrt{\frac\pi2}. $$