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

-
I think this math.stackexchange.com/questions/618077/… must help you. – user121270 May 25 '14 at 22:20
"Identity" would be a more apt word that "equation". An identity is an equality that is true regardless of the values of any free variables (in this case, $n$ is free). "Equation" is usually (not quite always) means an equality in which you're trying to figure out which values of any free variables make it true. – Michael Hardy May 25 '14 at 22:21
. . . and I just noticed that although you said "prove" in the subject line, you said "solve" in the body of the question. What you're talking about here is proving an identity, not solving an equation. – Michael Hardy May 26 '14 at 2:33

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.

-
the right side of your identity is not equal to what I wrote in the question. can I ask why? – user144555 May 25 '14 at 22:51
@Michael, I fixed a small error and added some explanation to address the query in the OP's comment. I hope you're OK with the edit. – Barry Cipra May 25 '14 at 23:24
I think Barry Cipra's edit may deal with the first comment above, except for this: never conclude that two things are not equal merely because they don't immediately look the same. – Michael Hardy May 26 '14 at 1:00

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.

-

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

-