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?
 A: 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.
A: 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.
