Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
1  
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

 
discard

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

Browse other questions tagged or ask your own question.