Thursday 21 May 2015

summation - 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?


Answer



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


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...