Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How can I show that k and n being integers

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

the following is true using a combination proof.

I am not sure how to do this. on the right hand side you have the set of n object and you are and out of the set (2n-1) object you chose n-1 and multiply by the set n.

On the right hand you chose a out n of object one item a k and square it and then multiply by this k object. For as many k item you have.

But how is it shown they equal?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

Here it goes:
Suppose there are $2n$ people, divided in two groups of $n$. We want to choose the same number of people $k$ ($1\leq k\leq n$) from both groups to play against each other in a match. For the first team, from the ones who play, we choose a leader. If we sum over all possibilities for $k$, we get the left hand side: $$ \sum_{k=1}^nk\binom{n}{k}^2 $$ We can also choose first pick a leader from the first $n$ people in $n$ ways. Then, we pick $n-1$ from the remaining $2n-1$ people. From the first half, we pick those people who will play and from the second half, we pick those people who won't play. Suppose we pick $k-1$ people from the first $n-1$ people. Then, $k$ people will play for the first team and $n-(n-1-(k-1))=k$ people will play for the second team. Thus, we count the same number of events as before. This yields the equality: $$ \sum_{k=1}^nk\binom{n}{k}^2=n\dbinom{2n-1}{n-1} $$

share|improve this answer
    
yes this makes perfecto sense but who are the 2n-1 people from which n-1 people are chosen are they one of the groups of the 2n people. –  Fernando Martinez Feb 21 at 22:54
    
@FernandoMartinez, the $2n-1$ people are just the $2n$ people, except the leader, who is already chosen at that point. –  Ragnar Feb 21 at 23:32

$\sum_{k=1}^nk\dbinom{n}{k}^2=\sum_{k=1}^nk\dbinom{n}{k}\dbinom{n}{n-k}$ is the number of ways of ways of choosing a set of $n$ balls from two collections A and B of $n$ of identical balls, and declaring a ball taken from A as a 'good' ball.Where the $k$-th term in the summation in LHS corresponds to the case: $k$ balls picked from A and $n-k$ picked from B, and choosing one of $k$ balls taken from A as the good ball.

The same thing can be done by first choosing a good ball from A in $n$ ways and choosing remaining $n-1$ balls from total $2n-1$ balls left in collections A and B, after removal.Which can be done in $n\dbinom{2n-1}{n-1}$ ways.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.