Problem
COM-B1-M03-P021 A Diagonal Sum in Pascal's Triangle
#21
★★★★☆ Level 4 of 5
Prove combinatorially that \(C(r,r)+C(r+1,r)+\cdots+C(n,r)=C(n+1,r+1)\).
Count \((r+1)\)-element subsets by their largest element.
Consider all \((r+1)\)-element subsets of \(\{1,\ldots,n+1\}\). There are \(C(n+1,r+1)\). If the largest element is \(t+1\), where \(r\le t\le n\), then the other \(r\) elements are chosen from the first \(t\) elements: \(C(t,r)\) ways. Summing over \(t\) gives the left side.
Good olympiad identity without algebra.