Thursday, 21 May 2015

summation - Error in a binomial coefficient sum identity proof



I have been given an identity ni=0i(ni)2=n(2n1n1).
However when I tried to prove it, I got a different result.

ni=0i(ni)2=nni=0(n1i1)(ni)=nni=0(n1ni)(ni)=n(2n1n)



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, ni people from the right wing, then the chief among the selected i people from the left wing. This leads to ni=0i(ni)(nni)=ni=0i(ni)2. The other approach is to select the chief from the left wing first (n ways for doing that), then select n1 people from the remaining 2n1 in the parliament. Conclusion:
ni=0i(ni)2=n(2n1n1)=n(2n1n).


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...