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.

  • $\begingroup$ Probably hard to do it by induction, even if you remove the $b$ from the denominator. $\endgroup$ – Thomas Andrews Oct 26 '15 at 18:46
  • 1
    $\begingroup$ 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 $$ $\endgroup$ – gt6989b Oct 26 '15 at 18:50
  • $\begingroup$ $a\cdot a!=(a+1)!-a!$ $\endgroup$ – 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.