2
$\begingroup$

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.

$\endgroup$
3
  • 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$ Apr 22, 2013 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, 2013 at 19:50
  • $\begingroup$ @Todd: Oren Patashnik is the name; also, that's the guy who (co-)made BibTeX, so .... :-) $\endgroup$
    – Suvrit
    Apr 22, 2013 at 21:26

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.