Задача
COM-B1-M03-P021 Сумма диагонали Паскаля
#21
★★★★☆ Уровень 4 из 5
Докажите комбинаторно тождество \(C(r,r)+C(r+1,r)+\cdots+C(n,r)=C(n+1,r+1)\).
Считайте \((r+1)\)-элементные подмножества по наибольшему элементу.
Рассмотрим все \((r+1)\)-элементные подмножества множества \(\{1,\ldots,n+1\}\). Их \(C(n+1,r+1)\). Если наибольший элемент равен \(t+1\), где \(r\le t\le n\), то остальные \(r\) элементов выбираются из первых \(t\) элементов: \(C(t,r)\) способов. Суммируя по \(t\), получаем левую часть.
Хорошая олимпиадная идентичность без алгебры.