Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 5 down vote accepted

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

share|cite|improve this answer
This is a pure beauty ! Thanks for that ! – Claude Leibovici Apr 27 '14 at 13:48
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 '14 at 18:00
@Bach Thanks. And you are quite correct about the typo. – Did Apr 27 '14 at 19:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.