# Combinatorics identity algebraic proof

Prove that:

$$\sum _{k=1}^n \:k\binom{n}{k}^2=n\binom {2n-1}{n-1}$$

I tried to prove it using induction:

For n+1:

\begin{align*} \sum_{k=1}^{n+1} \:k\binom{n+1}{k}^2 &= \sum \:k\left(\binom{n}{k}+\binom{n}{k-1}\right)^2 \:\left[Pascal's\:rule\right] \\ \\ &= \sum \:k\binom{n}{k}^2+\sum \:2k\binom{n}{k}\binom{n}{k-1}+\sum \:k\binom{n}{k-1}^2 \\ \\ &= n\binom{2n-1}{n-1} +\sum \:2k\binom{n}{k}\binom{n}{k-1} + n\binom{2n-1}{n-2} [*] \end{align*}

[*] - Induction hypothesis

Now I'm stuck with the middle expression.

Any advice on how to proceed would be appreciated.

Note: I'm looking for an algebraic proof not combinatorial interpretation.

## 2 Answers

$\sum k {n \choose k}^2 = \sum k {n \choose k} {n \choose n -k}$ combinatorial interpretation is that you have a group of $n$ men and $n$ women, you want to choose a team leader who has to be a man and $n-1$ team members - no matter what their gender is. your left hand side corresponds to first saying "ok - my group will have $k \geq 1$ men in it so I choose those men in ${n \choose k}$ ways, choose the leader from them in $k$ ways and then choose $n-k$ women to complete the team in ${n \choose n -k}$ ways. The right hand side corresponds to the method - first choose the leader from $n$ men in $n$ ways then choose the rest of the team $(n-1)$ people from a group of $2n - 1$ in ${2n -1 \choose n-1}$ ways

• I didn't look for the combinatorial interpretation (In the title I said algebraic proof) but thanks anyway. – GinKin Nov 17 '13 at 19:25
• sorry, didn't notice and I really like combinatorial proofs – mm-aops Nov 17 '13 at 19:26

You can prove it directly by using the identities

$$k\binom{n}k=n\binom{n-1}{k-1}$$

and

$$\sum_k\binom{m}k\binom{n}{\ell-k}=\binom{m+n}\ell\;;$$

the latter is Vandermonde’s identity. Both have nice combinatorial proofs that have appeared on this site.

\begin{align*} \sum_{k=1}^nk\binom{n}k^2&=\sum_{k=1}^nn\binom{n-1}{k-1}\binom{n}k\\\\ &=n\sum_{k=1}^n\binom{n-1}{k-1}\binom{n}{n-k}\\\\ &=n\sum_{k=0}^{n-1}\binom{n-1}k\binom{n}{n-1-k}\\\\ &=n\binom{2n-1}{n-1} \end{align*}

• This is really nice but we haven't covered these identities so I doubt we can use them. – GinKin Nov 17 '13 at 19:29
• @GinKin: You can always include their proofs. :-) (I’m just pointing out that the option is available, not saying that you necessarily should use it.) The first one is easily proved computationally just by manipulating factorials; Vandermonde’s is most easily proved combinatorially, as is done here, for instance. – Brian M. Scott Nov 17 '13 at 19:31
• I don't get what's inside the red line: i.imgur.com/I4IVfOP.jpg do you multiply the binoms to simplify them ? In the second line, how did $\binom {n}{n-k}$ get there ? How did you get rid of the sum ? Also, we have to strictly prove it algebraically, so using other identities and proving them combinatorially is not allowed. – GinKin Nov 17 '13 at 19:46
• @GinKin: $\binom{n}k=\binom{n}{n-k}$, so I replaced the second factor of $\binom{n}k$ by $\binom{n}{n-k}$. Then I shifted the index of summation by $1$. Finally, I used Vandermonde’s identity to get rid of the summation. (I will not say what I think of instructors who impose arbitrary restrictions on the kinds of argument allowed.) – Brian M. Scott Nov 17 '13 at 19:53