Problem
COM-B2-M03-P007 Pascal Identity
#7
★★★☆☆ Level 3 of 5
Prove by bijection the identity \(\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}\).
Split \(k\)-subsets according to whether they contain element \(n\).
All \(k\)-subsets of \([n]\) split into two classes. If a subset does not contain \(n\), it is a \(k\)-subset of \([n-1]\): \(\binom{n-1}{k}\) choices. If it contains \(n\), the remaining \(k-1\) elements are chosen from \([n-1]\): \(\binom{n-1}{k-1}\) choices. These classes are disjoint and cover all objects.
This is case splitting, but with an explicit bijection for each class.