# Asymptotic approximation of a certain sum

During calculations of an expectation of some random variable, I have encountered the following sum:

$$\sum_{t=2}^{n+1} \frac{t(t-1) \cdot n!}{(n-t+1)!\cdot n^t}$$

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}.$$
This is simply wonderful! I believe you have a typo there: $e^{-n}S_n=\ldots$ should be $e^{-n}U_n=\ldots$. –  Bach Apr 27 at 18:00