Задача
COM-B1-M04-P014 Сумма пар в начальных отрезках
#14
★★★☆☆ Уровень 3 из 5
Докажите, что \(C(2,2)+C(3,2)+\cdots+C(n,2)=C(n+1,3)\).
Считайте трёхэлементные подмножества по наибольшему элементу.
Выберем \(3\)-элементное подмножество из \(\{1,\ldots,n+1\}\). Если наибольший элемент равен \(t+1\), то остальные два выбираются из \(1,\ldots,t\), то есть \(C(t,2)\) способами. Сумма по \(t=2,\ldots,n\) даёт левую часть, а всего таких подмножеств \(C(n+1,3)\).
Hockey-stick через наибольший элемент.