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.

How can you calculate the asymptotics of $\sum_{i=0}^{n} \frac{i n^i}{i!}$ ? This sum looks similar to the power series for $e^n$. I have also seen similar problems solved using Poisson distributions Limit using Poisson distribution for example. However I cannot see how to handle the extra term.

share|improve this question
    
math.stackexchange.com/questions/268332/… Can this help? –  Alex Mar 10 '13 at 20:46
    
Not only the extra term: you also have $\,n\,$ both in the numerator of the series general tern and as the upper limit of the series... –  DonAntonio Mar 10 '13 at 20:47
    
@DonAntonio That's the same as in math.stackexchange.com/questions/160248/… isn't it? –  user66151 Mar 10 '13 at 20:53

1 Answer 1

up vote 2 down vote accepted

$$\sum_{i=0}^{n} \frac{i n^i}{i!} = \sum_{i=1}^{n} \frac{n^i}{(i-1)!} = \sum_{i=0}^{n-1} \frac{ n^{i+1}}{i!} = n\sum_{i=0}^{n-1} \frac{ n^{i}}{i!} $$

Since, as shown in the linked problem, $$e^{-n}\sum_{k=0}^n\frac{n^k}{k!} =\frac12+O(n^{-1/2}) $$

$$\sum_{i=0}^{n} \frac{i n^i}{i!} = n(\sum_{i=0}^{n} \frac{ n^{i}}{i!}-\frac{ n^{n}}{n!}), $$

so

$$\begin{align} e^{-n}\sum_{i=0}^{n} \frac{i n^i}{i!} &= e^{-n}n(\sum_{i=0}^{n} \frac{ n^{i}}{i!}-\frac{ n^{n}}{n!})\\ &=n(1/2 +O(n^{-1/2})) - n e^{-n}\frac{ n^{n}}{n!}\\ &= n/2 + O(n^{1/2}) - n \frac{(n/e)^n}{\sqrt{\pi}(1+O(1/n)) n^{n+1/2}/e^n}\\ &= n/2 + O(n^{1/2}) - n (n/e)^n/(\sqrt{\pi}(1+O(1/n)) n^{n+1/2}/e^n)\\ &= n/2 + O(n^{1/2}) - n^{1/2}(1+O(1/n))/\sqrt{\pi}\\ &= n/2 + O(n^{1/2}) \end{align} $$

share|improve this answer

Your Answer

 
discard

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