For the first part (The combinatorial form): Suppose you have a group consisting of n boys and n girls. A team of n has to be formed out of them, and a captian designated of the team, which has to be a girl. On one hand, one can fix the number k of girls and n−k of boys on the team first, then choose the team in one of ${n\choose k}{n \choose n−k}$ ways and a captain in one of k ways, so the left hand side counts the number of possible selections. On the other hand one could start out to choose one of the n girls as captain, and let her choose n−1 team mates among the remaining 2n−1 children; this is counted by the right hand side.

But I can´t find an example for the set form. Any tips for that?

  • 2
    $\begingroup$ When you say "prove with sets" and "set form," what are you looking for exactly? $\endgroup$ – Mike Earnest Sep 25 '17 at 23:19

$$\sum_{k=0}^n k\binom nk^2=\sum_{k=0}^n k\binom nk\binom n{n-k}=n\sum_{k=0}^n\binom {n-1}{k-1}\binom n{n-k}=n\binom {2n-1}{n-1}$$


One has $$(x+1)^n = \sum_{k=0}^n {n \choose k}x^k$$ Then $$n(x+1)^{n-1} = \sum_{k=1}^n k{n \choose k}x^{k-1}$$

So $$n(x+1)^{2n-1} = \left(\sum_{k=0}^n {n \choose k}x^k\right)\left(\sum_{k=1}^n k{n \choose k}x^{k-1}\right)$$

The coefficient of $x^{n-1}$ in the LHS is $n{2n-1\choose n-1}$, and in the RHS is $\sum_{k=0}^n k{n\choose k}{n\choose n-k}$.

  • $\begingroup$ In your second line, you meant to write $$n(x + 1)^{n - 1} = \sum_{k = 1}^{n} \color{red}{k}\binom{n}{k}x^{k - 1}$$ $\endgroup$ – N. F. Taussig Sep 26 '17 at 8:28
  • $\begingroup$ My mistake. Thanks. $\endgroup$ – GAVD Sep 26 '17 at 8:29

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.