Problem
COM-B1-M04-P014 Sum of Pairs in Initial Segments
#14
★★★☆☆ Level 3 of 5
Prove that \(C(2,2)+C(3,2)+\cdots+C(n,2)=C(n+1,3)\).
Count three-element subsets by their largest element.
Choose a three-element subset of \(\{1,\ldots,n+1\}\). If the largest element is \(t+1\), the other two are chosen from \(1,\ldots,t\), in \(C(t,2)\) ways. Summing over \(t=2,\ldots,n\) gives the left side, while the total number is \(C(n+1,3)\).
Hockey-stick identity via largest element.