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:

enter image description here

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

  • $\begingroup$ This is a pure beauty ! Thanks for that ! $\endgroup$ – Claude Leibovici Apr 27 '14 at 13:48
  • $\begingroup$ This is simply wonderful! I believe you have a typo there: $e^{-n}S_n=\ldots$ should be $e^{-n}U_n=\ldots$. $\endgroup$ – Bach Apr 27 '14 at 18:00
  • $\begingroup$ @Bach Thanks. And you are quite correct about the typo. $\endgroup$ – Did Apr 27 '14 at 19:59

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.