# Prove using combinatorics$\sum_{r=0}^n\binom{2n}{r}^2=\frac{1}{2}(\binom{4n}{2n}-\binom{2n}{n}^2)$

Prove using combinatorics:

$$\sum_{r=0}^n\binom{2n}{r}^2=\frac{1}{2}(\binom{4n}{2n}-\binom{2n}{n}^2)$$

LHS:Consider $2n$ girls and $2n$ boys we can choose not $r$ boys and choose $r$ girls so we made a $2n$ person team from $4n$ persons that $n(girls)\ge n(boys)$.

RHS:We choose $2n$ persons from $2n$ girls and $2n$ boys we reduce the case $n(boys)=n(girls)$ and by symmetry in the half of the others we have $n(boys)<n(girls)$.

But the problem is that in the LHS we can have equality case but in the RHS we can't.Where did I make a mistake?

## 2 Answers

If $n=1$, then

$$\sum_{r=0}^n{2n\choose r}^2={2\choose0}^2+{2\choose1}^2=1+4=5$$

whereas

$${1\over2}({4n\choose2n}-{2n\choose n}^2)={1\over2}({4\choose2}-{2\choose1}^2)={1\over2}(6-4)=1$$

so something is wrong in the identity you're trying to prove.

Added later: I believe the correct identity is

$$\sum_{r=0}^n{2n\choose r}^2={1\over2}({4n\choose2n}+{2n\choose n}^2)$$

which you can prove combinatorially by first rewriting it as

$$\sum_{r=0}^n{2n\choose r}{2n\choose2n-r}+\sum_{r=0}^n{2n\choose2n-r}{2n\choose r}={4n\choose2n}+{2n\choose n}{2n\choose n}$$

The first sum on the left hand side counts the number of ways to choose, from a class of $2n$ girls and $2n$ boys, a group of size $2n$ with no more girls than boys; the second sum counts the same, but with no more boys than girls. But this counts all ways of choosing a group of size $2n$ from the total class of $4n$ girls and boys, with the groups that have equally many girls and boys counted twice. And that's what the formula on the right hand side expresses.

the correct identity is $$\sum_{r=0}^n \binom{2n}{r}^2 = \frac{1}{2} \left( \binom{4n}{2n} + \binom{2n}{n}^2\right).$$ The combinatorial interpretation of the LHS is to choose from $2n$ boys and $2n$ girls a team of $2n$ people, in which there are at most $n$ boys on the team. This is because $$\binom{2n}{r} = \binom{2n}{2n-r}.$$

Clearly, if there is no restriction on the number of boys, the total number of ways is simply $$\binom{4n}{2n},$$ since you can choose $2n$ people out of $4n$ people. But due to symmetry between boys and girls, you can say "either at most $n$ boys are on the team," or "either at most "n" girls are on the team," but in each case one has counted the case where there are exactly $n$ boys and $n$ girls. So if we rearrange the identity as $$\binom{4n}{2n} = -\binom{2n}{n}^2 + 2 \sum_{r=0}^n \binom{2n}{r}^2,$$ the combinatorial interpretation is obvious: the LHS is the counting of the number of $2n$-person teams out of $2n$ boys and $2n$ girls without restriction; the sum on the RHS counts the number of ways to pick a $2n$-person team with at most $n$ boys, and twice this is the number of ways to pick a $2n$-person team with at most $n$ boys or at most $n$ girls; we then need to subtract the case we have double-counted, in which exactly $n$ boys and $n$ girls are selected.

• Ah, I was editing my answer while you posted yours. Great minds, and all that.... – Barry Cipra Apr 7 '17 at 19:44