Prove this equation - combinatorics I tried to solve this equation without success.
anyone know how to do it?
$$
\sum_{k=0}^n k \binom n k^{2} = n \binom{2n-1}{n-1}
$$
 A: A committee consists of $n$ Democrats and $n$ Republicans.  You will randomly choose $k$ of the Democrats and $n-k$ of the Republicans for a subcommittee.  The number of ways to do that is 
$$
\sum_{k=0}^n \binom n k \binom n {n-k} = \sum_{k=0}^n {\binom n k}^2.
$$
The probability that you get exactly $k$ Democrats is
$$
\frac{{\dbinom n k}^2}{\dbinom{2n}{n}}
$$
since the denominator is the total number of ways to choose $n$ out of $2n$.
The expected number of Democrats is $n/2$, by symmetry.  Hence
$$
\sum_{k=0}^n k\Pr(\text{number of Democrats}=k) = \frac n 2.
$$
Thus
$$
\sum_{k=0}^n k {\binom n k}^2 = \frac n 2 \binom{2n}{n}.
$$
Finally, note that
$$\binom{2n}{n}=\binom{2n-1}{n}+\binom{2n-1}{n-1}=2\binom{2n-1}{n-1}$$
using standard identities for binomial coefficients.
A: Here's an approach using generating functions.  By the binomial theorem,
$$
\sum_{k=0}^n \binom{n}{k} x^k = (1 + x)^n \, .
$$
Differentiating the above and then multiplying by $x$, we have
$$
\sum_{k=0}^n k \binom{n}{k} x^{k} = nx(1+x)^{n-1} \, .
$$
Let $[x^m] f(x)$ denote the coefficient of $x^m$ in $f(x)$.  By the convolution formula for ordinary generating functions, then
\begin{align*}
\sum_{k=0}^n k \binom{n}{k}^2 &=\sum_{k=0}^n k \binom{n}{k} \binom{n}{n-k}= [x^n] \left(nx(1+x)^{n-1}\right) (1+x)^n\\
&= [x^{n-1}] n (1+x)^{2n-1} = n \binom{2n-1}{n-1}
\end{align*}
as desired.
A: And here's another proof using binomial theorem. Let 
$$S=\sum\limits_{k=0}^n k {n \choose k}^2$$
Therefore 
$$S=0 {n \choose 0}^2+1  {n \choose 1}^2 + \cdots + n {n \choose n}^2$$
Since ${n \choose k}={n \choose n-k}$, we can reverse the sum and add it to itself, which gives us
$$2S=(0+n ){n \choose 0}^2+ (1+(n-1))  {n \choose 1}^2 + \cdots + (n+0 ){n \choose n}^2$$
$$2S=n \left( {n \choose 0}^2+  {n \choose 1}^2 + \cdots + {n \choose n}^2 \right)$$
Now, look at the binomial expansion of $(1+x)^n$ and $(x+1)^n$.
$$(1+x)^n={n \choose 0}x^0+{n \choose 1}x^1 + \cdots + {n \choose n}x^n$$
$$(x+1)^n={n \choose 0}x^n+{n \choose 1}x^{n-1} + \cdots + {n \choose n}x^0$$
It's clear now that in the product of the above 2 expressions, the coeffecient of $x^n$ will be $$ {n \choose 0}^2+  {n \choose 1}^2 + \cdots + {n \choose n}^2$$.
Therefore 
$$ {n \choose 0}^2+  {n \choose 1}^2 + \cdots + {n \choose n}^2= {2n \choose n}$$
Hence
$$S=\frac{n}{2}{2n \choose n}=n{2n-1 \choose n-1}$$
