Problem
COM-B2-M01-P005 A Marked Element
#5
★★☆☆☆ Level 2 of 5
Prove \(\sum_{k=0}^n k\binom nk=n2^{n-1}\).
Count pairs \((A,x)\), where \(x\in A\).
If we first choose \(A\) of size \(k\), then the marked element \(x\in A\) can be chosen in \(k\) ways, giving the left side. If we first choose \(x\), there are \(n\) choices, and the remaining elements of the subset are chosen freely: \(2^{n-1}\) choices. This gives \(n2^{n-1}\).
The first important identity through pairs.