MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have derived two different solutions to the same problem involving computing the expected time to find $k$ swaps when collecting coupons. However to me the two sums, although apparently numerically identical, look completely unrelated. Is there some elementary way of showing the following identity? $$\sum_{s=1}^n(s+m) \binom{n}s \sum_{i=0}^s(-1)^i\binom{s}i \left(\frac{s-i}n\right)^{s+m-1}\frac{s}n=n + m - \sum_{k=1}^{n} k^{k-1} \binom{n}{k} \frac{(n-k)^{n+m-k}}{n^{n+m-1}} $$

This is defined for integers $n,m \geq 1$.

This is related to a possibly simpler previous question I asked.

share|cite|improve this question
A proof of the form "They count the same thing in two ways" is about as good as it gets in my opinion. – Aaron Meyerowitz Apr 22 '13 at 3:26
Following on Aaron's comment: it sounds like you've already answered your own question! That is, assuming your solutions were correctly derived, you've already given a proof of the identity yourself. Did I misunderstand? Follow-up question: are you familiar with the usual techniques as set out in Concrete Mathematics by Graham, Knuth, and the last guy whose name I forget? (Otashnik or something) – Todd Trimble Apr 22 '13 at 19:50
@Todd: Oren Patashnik is the name; also, that's the guy who (co-)made BibTeX, so .... :-) – Suvrit Apr 22 '13 at 21:26
Thanks Suvrit; I didn't know that about him. – Todd Trimble Apr 22 '13 at 23:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.