Problem
COM-B1-M03-P013 Pascal's Identity
#13
★★★☆☆ Level 3 of 5
Prove combinatorially that \(\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}\).
Fix one special element.
Count \(k\)-element subsets of an \(n\)-element set. The special element is either not chosen: \(\binom{n-1}{k}\), or chosen: \(\binom{n-1}{k-1}\). The sum of these disjoint cases gives all subsets.
Very important idea-proof, not algebra.