# Error in a binomial coefficient sum identity proof

I have been given an identity \begin{align} \sum_{i=0}^n i\binom{n}{i}^2 = n\binom{2n-1}{n-1} \end{align}. However when I tried to prove it, I got a different result. \begin{align} \sum_{i=0}^n i\binom{n}{i}^2 = n\sum_{i=0}^n \binom{n-1}{i-1} \binom{n}{i} = n\sum_{i=0}^n \binom{n-1}{n-i} \binom{n}{i} = n\binom{2n-1}{n} \end{align}

First equation follows from absorption identity, second one from symmetry, and the third one from Vandermonde's identity. Where is my mistake?

• I think you'd find that $\binom{n}{k}=\binom{n}{n-k}$ that should help to some extent. – user451844 Aug 11 '17 at 16:56

Let us devise a purely combinatorial approach: assume to have a parliament with $n$ people in the right wing, $n$ people in the left wing. In how many ways can we form a committee with $n$ people and elect a chief of the commitee from the left wing? The first approach is to select $i$ people from the left wing, $n-i$ people from the right wing, then the chief among the selected $i$ people from the left wing. This leads to $\sum_{i=0}^{n}i\binom{n}{i}\binom{n}{n-i}=\sum_{i=0}^{n}i\binom{n}{i}^2$. The other approach is to select the chief from the left wing first ($n$ ways for doing that), then select $n-1$ people from the remaining $2n-1$ in the parliament. Conclusion: $$\sum_{i=0}^{n}i\binom{n}{i}^2 = n\binom{2n-1}{n-1} = n\binom{2n-1}{n}.$$

• +1 for making me realize (along with @Roddy MacPhee) that $2n-1-(n-1)=n$ :P – Joald Aug 11 '17 at 17:09


If one takes $n=2$ then $$\sum_{i=0}^n i\binom{n}i^2=0+\binom21^2+2\binom22^2=4+2=6$$ and $$\binom{2n-1}{n-1}=\binom{3}1=3.$$ It seems in this case that $\sum_{i=0}^n i\binom{n}i^2$ equals $n\binom{2n-1}n$ rather than $\binom{2n-1}{n-1}$.

The question as stated is incorrect; here's a combinatorial proof for your version (the $n\binom{2n-1}{n}$ version):

Suppose we have $n$ turtles and $n$ rabbits at a sports meet. How many ways can we choose two teams of $n$ animals each, one of which has a captain (who must be a turtle)?

The LHS counts this directly by counting the number of ways to choose $i$ turtles to include and $i$ rabbits to exclude from the team with a captain, and picking a captain from among these turtles. The other team is composed of the remaining animals.

The RHS first picks the captain, then chooses $n$ of the other animals to form the other team. The remaining animals join the captain's team.

• the two results are the same – G Cab Aug 11 '17 at 17:17