I have been given an identity n∑i=0i(ni)2=n(2n−1n−1).
However when I tried to prove it, I got a different result.
n∑i=0i(ni)2=nn∑i=0(n−1i−1)(ni)=nn∑i=0(n−1n−i)(ni)=n(2n−1n)
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 ∑ni=0i(ni)(nn−i)=∑ni=0i(ni)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:
n∑i=0i(ni)2=n(2n−1n−1)=n(2n−1n).
No comments:
Post a Comment