$$\sum_{n=1}^m \frac{n \cdot n! \cdot \binom{m}{n}}{m^n} = ?$$
My attempts on the problem:
I tried writing out the summation.
$$1+\frac{2(m+1)}{m} + \frac{3(m-1)(m-2)}{m^2} + \cdots + \dfrac{m\cdot m!}{m^m}$$
I saw that the ratio between each of the terms is $\dfrac{\dfrac{n}{n-1} (m-n+1)}{m}$
I wasn't able to proceed because this isn't a geometric series. Please help!
I would appreciate a full solution if possible.
Answer
Expanding the binomial ${m\choose n} = \frac{m!}{(m-n)!n!}$ your sum can be written
$$m!\sum_{n=1}^m \frac{1}{(m-n)!}\frac{n}{m^n}$$
We can now change the summation index $i = m-n$ (i.e. summing from $m$ down to $0$) to get
$$\frac{m!}{m^m}\sum_{i=0}^{m-1} \frac{m^i}{i!}(m-i) = \frac{m!}{m^m}\left[\sum_{i=0}^{m-1} m^{i+1}\frac{1}{i!} - \sum_{i=0}^{m-1} m^i\frac{i}{i!}\right]$$
Now use $\frac{i}{i!} = \frac{1}{(i-1)!}$ and change the summation index $j=i-1$ in the last sum and you will see that most of the terms will cancel giving you a simple result ($=m$).
No comments:
Post a Comment