# Proving that $\sum_{a=1}^{b} \frac{a \cdot a! \cdot \binom{b}{a}}{b^a} = b$

Prove that for all positive integers $b$ that $$\sum_{a=1}^{b} \frac{a \cdot a! \cdot \binom{b}{a}}{b^a} = b.$$

My idea is induction, but I cannot figure stuff out on the inductive step.

• Probably hard to do it by induction, even if you remove the $b$ from the denominator. – Thomas Andrews Oct 26 '15 at 18:46
• Perhaps you could expand $\binom{b}{a}$ and cancel it with $a!$, grouping the resulting terms, but not sure what to do with it:$$a \binom{b}{a} \frac{a!}{b^a} = a \frac{b!}{a! (b-a)!} \frac{a!}{b^a} = a \frac{(b-1)!}{(b-a)!b^{a-1}} = a \prod_{k=b-a+1}^{b-1} k$$ – gt6989b Oct 26 '15 at 18:50
• $a\cdot a!=(a+1)!-a!$ – Lucian Oct 26 '15 at 23:33

Consider an urn with $b$ distinct balls, and we draw these balls randomly, one at a time, with replacement. We stop when we get a ball that has been previously drawn. Let $A$ be the random variable that counts the number of distinct balls drawn during the experiment. Then for $a=1,2,\dots, b$ we have $$P(A=a)={b\over b}{b-1\over b}\cdots {b-a+1\over b}{a\over b}.$$
Since the probabilities must add to one, we get the desired equation $$1=\sum_{a=1}^b {b\over b}{b-1\over b}\cdots {b-a+1\over b}{a\over b}.$$
This can be reduced to a telescoping sum. \begin{align} \sum_{a=1}^b\frac{a\cdot a!\binom{b}{a}}{b^a} &=\sum_{a=1}^b\frac{[b-(b-a)]\frac{b!}{(b-a)!}}{b^a}\tag{1}\\ &=\sum_{a=1}^b\frac{\frac{b!}{(b-a)!}}{b^{a-1}}-\sum_{a=1}^{b-1}\frac{\frac{b!}{(b-a-1)!}}{b^a}\tag{2}\\ &=\sum_{a=1}^b\frac{\frac{b!}{(b-a)!}}{b^{a-1}}-\sum_{a=2}^b\frac{\frac{b!}{(b-a)!}}{b^{a-1}}\tag{3}\\ &=\frac{\frac{b!}{(b-1)!}}{b^{1-1}}\tag{4}\\[12pt] &=b\tag{5} \end{align} Explanation:
$(1)$: $a=b-(b-a)$ and $a!\binom{b}{a}=\frac{b!}{(b-a)!}$
$(2)$: left sum: $\frac{b}{b^a}=\frac1{b^{a-1}}$
$\phantom{\text{(2):}}$ right sum: $(b-a)\frac{b!}{(b-a)!}=\frac{b!}{(b-a-1)!}$, removing the $a=b$ term
$(3)$: right sum: substitute $a\mapsto a-1$
$(4)$: all terms cancel except for the $a=1$ term in the left sum
$(5)$: evaluate