# Find the sum $\sum _{ k=1 }^{ 100 }{ \frac { k\cdot k! }{ { 100 }^{ k } } } \binom{100}{k}$

Find the sum $$\sum _{ k=1 }^{ 100 }{ \frac { k\cdot k! }{ { 100 }^{ k } } } \binom{100}{k}$$

When I asked my teacher how can I solve this question he responded it is very hard, you can't solve it. I hope you can help me in solving and understanding the question.

• If you can edit the title . I will be very grateful – Algorthim era Jan 30 '16 at 8:55
• Thanks for correcting my errors . I will review your edit – Algorthim era Jan 30 '16 at 8:58
• I got it from internet . We are studying the summation and I would like to be perfect in this part of mathematic . so , the questions in my book are very easy. for this reason , I would like to improve my self by the questions in the internet – Algorthim era Jan 30 '16 at 9:04
• I know the solution . I wanna know the way of solving this question – Algorthim era Jan 30 '16 at 9:09
• You mean you know the sum, but want to know the solution? – alex.jordan Jan 30 '16 at 9:10

\begin{align} \sum\limits_{k=1}^{100} \frac {k\cdot k!}{100^k} \frac{100!}{k!(100-k)!} &= \frac{100!}{100^{100}} \sum\limits_{k=1}^{100} \frac{k\cdot100^{100-k}}{(100-k)!}\\ &= \frac{100!}{100^{100}} \sum\limits_{k=0}^{99}\frac{(100-k)\cdot 100^k}{k!}\\ &=\frac{99!}{100^{99}} \sum\limits_{k=0}^{99} \left( \frac {100^{k+1}}{k!} - \frac{100^k}{(k-1)!}\right)\\ &= \frac{99!}{100^{99}} \left(\frac{100^1}{0!}+ \sum\limits_{k=1}^{99} \frac {100^{k+1}}{k!} - \sum\limits_{k=0}^{98} \frac{100^{k+1}}{k!}\right)\\&= \frac{99!}{100^{99}} \left(\frac{100^1}{0!}+ \frac{100^{100}}{99!} + \sum\limits_{k=1}^{98} \frac {100^{k+1}}{k!} - \sum\limits_{k=1}^{98} \frac{100^{k+1}}{k!} -\frac{100^1}{0!} \right)\\ &= 100 \end{align}

• of course. I think my teacher can't solve it – Algorthim era Jan 30 '16 at 9:24
• Now one only needs to show that $100-99!/(100)^{98}=100$ – Pierpaolo Vivo Jan 30 '16 at 9:24
• $\frac{99!}{100^{98}}\approx 9.33\times 10^{-41}\neq 0$ – Claude Leibovici Jan 30 '16 at 9:27
• How can I show that – Algorthim era Jan 30 '16 at 9:27
• It seems that if you replace all instances of $100$ with $N$ you get $\sum _{ k=1 }^{ N }{ \frac { k\cdot k! }{ { N }^{ k } } } \binom{N}{k} = N$ – e2-e4 Jan 30 '16 at 12:16

Using the notation $n^\underline{r}=\overbrace{n\ (n-1)\ (n-2)\cdots(n-r+1)}^{r\text{ terms}}$ for the falling factorial , we have

\begin{align} \sum_{k=1}^n\frac {k\cdot k!}{n^k}\binom nk&= \sum_{k=1}^n\frac {\color{blue}k\cdot k!}{n^k}\cdot \frac {n^\underline{k}}{k!}\\ &=\sum_{k=1}^n\frac {n^\underline{k}}{n^k}\color{blue}{[n-(n-k)]}\\ &=n\underbrace{\sum_{k=1}^n\frac {n^\underline{k}}{n^k}-\frac{n^\underline{k+1}}{n^{k+1}}}_{\text{telescoping sum}} &&\text{as }n^\underline{k}(n-k)=n^\underline{k+1}\\ &=n &&\text{as }n^{\underline{n+1}}=0 \end{align}

Putting $n=100$ gives $$\sum_{k=1}^{100}\frac {k\cdot k!}{100^k}\binom {100}k=100\qquad\blacksquare$$

I am re-editing a-rodin's answer, correcting a few typos [of an earlier version, now edited].

\begin{align} \sum\limits_{k=1}^{100} \frac {k\cdot k!}{100^k} \frac{100!}{k!(100-k)!} &= \frac{100!}{100^{100}} \sum\limits_{k=1}^{100} \frac{k\cdot100^{100-k}}{(100-k)!}\\ &= \frac{100!}{100^{100}} \sum\limits_{k=0}^{99}\frac{(100-k)\cdot 100^k}{k!}\\ &=\frac{100!}{100^{100}} \sum\limits_{k=1}^{99} \left( \frac {100^{k+1}}{k!} - \frac{100^k}{(k-1)!}\right)+\frac{100!}{100^{99}}\\ &= \frac{100!}{100^{100}} \left( \sum\limits_{k=1}^{99} \frac {100^{k+1}}{k!} - \sum\limits_{k=0}^{98} \frac{100^{k+1}}{k!}\right)+\frac{100!}{100^{99}}\\&= \frac{100!}{100^{100}} \left( \frac{100^{100}}{99!} + \sum\limits_{k=1}^{98} \frac {100^{k+1}}{k!} - \sum\limits_{k=1}^{98} \frac{100^{k+1}}{k!} -\frac{100^1}{0!} \right)+\frac{100!}{100^{99}}\\ &= 100-\frac{100!}{100^{99}}+\frac{100!}{100^{99}}=100. \end{align}

• Yes, I see. I fixed my answer too. Thank you. – Alexander Rodin Jan 30 '16 at 10:17
• No problem. Nice answer, btw (+1). – Pierpaolo Vivo Jan 30 '16 at 10:19