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.

  • 1
    $\begingroup$ A proof of the form "They count the same thing in two ways" is about as good as it gets in my opinion. $\endgroup$ – Aaron Meyerowitz Apr 22 '13 at 3:26
  • 1
    $\begingroup$ 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) $\endgroup$ – Todd Trimble Apr 22 '13 at 19:50
  • $\begingroup$ @Todd: Oren Patashnik is the name; also, that's the guy who (co-)made BibTeX, so .... :-) $\endgroup$ – Suvrit Apr 22 '13 at 21:26

Your Answer

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

Browse other questions tagged or ask your own question.