Prove using combinatorics:


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?


If $n=1$, then

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


$${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.

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

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.