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.

Is it true that $\sum_kk\binom{n}{k}^2=n\binom{2n-1}{n-1}$? (I proved it using generating functions). Could you help me to prove it combinatorially? please

share|improve this question
    
It is wrong for $n=0$. –  Phira Nov 1 '11 at 0:12
    
It’s also wrong for $n=1,2$ and $3$: $1\ne 2+1$, $6\ne 6+6$, and $30\ne 20+30$. But notice that the second term on the right does agree with the lefthand side in these cases (and also in the $n=0$ case that @Phira mentioned). –  Brian M. Scott Nov 1 '11 at 0:24
    
I edited the question, I hope now it's right –  Alex M Nov 1 '11 at 0:24
    
That’s the answer that I got to your first question; it would be nice if you wrote up your generating function solution as an answer to that question. –  Brian M. Scott Nov 1 '11 at 0:27
add comment

3 Answers 3

up vote 3 down vote accepted

To obtain this combinatorially write left hand side as $\sum_k k {n \choose k} {n \choose n-k}$. This sum can be interpreted as the number of ways to choose $n$ children from a group of $n$ boys and $n$ girls ($2n$ children) and then choosing "leader" from, e.g., chosen boys.

On the other way it can be done as follows: choose a "leader" from boys group and then choose $n-1$ children from whole group of $2n-1$. That is $n {2n-1 \choose n-1}$.

share|improve this answer
add comment

$\sum_k k\binom{n}{k}^2$ and $n\binom{2n-1}{n-1}$ both count

The number of ways you can arrange $n$ black balls, $n-1$ white balls and $1$ red ball in two rows of $n$ balls each such that the red ball is in the lower row.

This is most easily seen for $n\binom{2n-1}{n-1}$ -- the factor of $n$ is for deciding where the red ball goes, and the binomial coefficient then distributes the black and white ones among the non-red places.

On the other hand, for $\sum_k k\binom{n}{k}^2$ choose, in order:

  • the number of black balls in the top row. This is the $k$ summed over.
  • the places in the top row that have black balls, for a factor of $\binom{n}{k}$.
  • the places in the bottom row that have black balls, a factor of $\binom{n}{n-k}=\binom{n}{k}$.
  • which of the remaining $k$ places in the bottom row will hold the red ball, for a factor of $k$.
share|improve this answer
    
You may want to delete that first sentence, now that Alex has fixed the problem statement. –  Brian M. Scott Nov 1 '11 at 0:36
add comment

For a combinatorial argument, imagine that you have $n$ men and $n$ women. From this group of $2n$ people you want to pick a team of $n$ people and choose one of the women on the team as captain. The two sides count the number of ways to do this. (On the lefthand side you’ll want to change one of the factors of $\binom{n}k$ to $\binom{n}{n-k}$.)

share|improve this answer
add comment

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.