Pascal's Rule

\[\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\]

Say we are counting the number of ways to choose a set \(S\) of size \(k\) from \(n\) elements. Fix any element \(x\). I can either include it in \(S\), in which case I have \(\binom{n-1}{k-1}\) ways to choose the remaining elements, or I can exclude it, in which case I have \(\binom{n-1}{k}\) ways to choose the remaining elements.