パスカルの恒等式

第1段階(1つの要素を固定し、含むかどうかで分ける):$n$ 個の対象のうち1つの対象 $x$ を固定する。$k$ 個の部分集合はそれぞれ $x$ を含むか含まないかのいずれかであり、この2つの場合は互いに素で、合わせて $C_n^k$ 個の部分集合すべてを覆う。

第2段階(xを含む部分集合を数える):$x$ を含む部分集合は、残りの $n-1$ 個の対象から $k-1$ 個を選ぶことで作られ、そのような部分集合は $C_{n-1}^{k-1}$ 個ある。

第3段階(xを含まない部分集合を数える):$x$ を含まない部分集合は、残りの $n-1$ 個の対象から $k$ 個すべてを選ぶことで作られ、そのような部分集合は $C_{n-1}^k$ 個ある。

第4段階(加法の法則を適用する):この2つの場合は互いに素であり、サイズkのすべての部分集合を尽くすので、加法の法則により $C_n^k = C_{n-1}^{k-1} + C_{n-1}^k$ が得られる。