2

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

Jacob Copland
  • 27

1 Answers1

1

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

Kibble
  • 1,157
  • How would the last equation simplify? – Jacob Copland Nov 16 '15 at 02:05
  • @JacobCopland First of all the $i=0$ term in the last sum is zero so we can start the sum at $i=1$. Then take $j=i-1$ and compare this to the first sum (most of the terms in the last sum is in the first sum so they will cancel) leaving you with only $1$ term. – Kibble Nov 16 '15 at 02:10
  • Can you actually do the substitution and simplication for me? I'm not really catching on to what you are saying. Sorry!!! – Jacob Copland Nov 16 '15 at 03:04
  • @JacobCopland For the latter sum we have $\sum_{i=0}^{m-1}m^i \frac{i}{i!} = \sum_{i=1}^{m-1}m^i \frac{i}{i!} = \sum_{j=0}^{m-2}m^{j+1} \frac{1}{j!} = \sum_{i=0}^{m-2}m^{i+1} \frac{1}{i!}$. Do you see now that this is almost the same as the first sum? We get $\frac{m!}{m^m}\left[\sum_{i=0}^{m-1}m^{i+1} \frac{1}{i!} - \sum_{i=0}^{m-2}m^{i+1} \frac{1}{i!}\right] = \frac{m!}{m^m}\cdot \frac{m^m}{(m-1)!} = m$ – Kibble Nov 16 '15 at 03:35