1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

$\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

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

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*}$$

$\endgroup$
  • $\begingroup$ This is really nice but we haven't covered these identities so I doubt we can use them. $\endgroup$ – GinKin Nov 17 '13 at 19:29
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Nov 17 '13 at 19:31
  • $\begingroup$ 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. $\endgroup$ – GinKin Nov 17 '13 at 19:46
  • 1
    $\begingroup$ @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.) $\endgroup$ – Brian M. Scott Nov 17 '13 at 19:53

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.