Problem
COM-B1-M04-P013 General Identity on Subset Sizes
#13
★★★☆☆ Level 3 of 5
Prove combinatorially that \(\sum_{k=0}^n kC(n,k)=n2^{n-1}\).
Count pairs \((S,x)\), where \(x\in S\).
By size \(S=k\): there are \(C(n,k)\) subsets and \(k\) choices of the marked element, giving the left side. By marked element: \(n\) choices for \(x\), and the other \(n-1\) elements are chosen freely for \(S\), \(2^{n-1}\) ways. This gives the right side.
Key identity of the module.