Problem
COM-B2-M01-P009 Two Marked Points
#9
★★★☆☆ Level 3 of 5
Prove the identity \(\sum_{k=0}^n \binom{k}{2}\binom nk=\binom n2 2^{n-2}\).
Count a subset together with a marked pair inside it.
Count pairs \((A,\{x,y\})\), where \(A\subseteq[n]\) and \(x,y\in A\). If we first choose \(A\) of size \(k\), we get \(\binom{k}{2}\binom nk\). Summing over \(k\) gives the left side. If we first choose \(\{x,y\}\), there are \(\binom n2\) choices, and the remaining \(n-2\) elements are free: \(2^{n-2}\) choices.
This is the first step toward counting triples and intersections.