Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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

Your Answer

 
discard

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.