# Pascal's Rule

## 1. Statement

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

## 2. Intuition

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.