\begin{equation}
{}_n C_r = +{}_{n -1} C_r +{}_{n -1} C_{r -1}
\end{equation}
個から
個を取り出す組合せと
個から
個を取り出す組合せの和は、
個から
個を取り出す組合せに等しい、というものです。
二項定理から導くこともできます。
二項定理 - 数式で独楽する
\begin{eqnarray}
(a+b)^n &=& \sum_{r=0}^n {}_n C_r \ a^{n-r} b^r \\
&=& {}_n C_0 \ a^n+{}_n C_1 \ a^{n-1} b+{}_n C_2 \ a^{n-2} b^2+\cdots +{}_n C_n \ b^n
\end{eqnarray}において
\begin{eqnarray}
a &=& 1 \\
b &=& x \\
\end{eqnarray}とします。
\begin{equation}
(1 +x)^n = {}_n C_0 +{}_n C_1 \ x +\cdots +{}_n C_r \ x^r +\cdots +{}_n C_n \ x^n \tag{1}
\end{equation}となります。
一方、
\begin{eqnarray}
(1 +x)^n &=& (1 +x)(1 +x)^{n -1} \\
&=& (1 +x)({}_{n -1} C_0 +{}_{n -1} C_1 \ x +\cdots +{}_{n -1} C_{r -1} \ x^{r -1} + {}_{n -1} C_r \ x^r +\cdots +{}_{n -1} C_{n -1} \ x^n) \\
&=& {}_{n -1} C_0 +{}_{n -1} C_1 \ x +\cdots + {}_{n -1} C_r \ x^r +\cdots +{}_{n -1} C_{n -1} \ x^{n -1} \\
&& \qquad \quad +{}_{n -1} C_0 \ x +\cdots +{}_{n -1} C_{r -1} \ x^r +\cdots +{}_{n -1} C_{n -2} \ x^{n -1}+{}_{n -1} C_{n -1} \ x^n \tag{2}
\end{eqnarray}とも書けます。
式(1), (2)のの係数を比較して、
\begin{equation}
{}_n C_r = {}_{n -1} C_r +{}_{n -1} C_{r -1}
\end{equation}を得ます。
