組合せに関する公式 ${}_{n+1}\mathrm{C}_{r+1}$ $= {}_n\mathrm{C}_{r}$ $+ {}_n\mathrm{C}_{r+1}$ の証明
組合せに関する公式 ${}_{n+1}\mathrm{C}_{r+1}$ $= {}_n\mathrm{C}_{r}$ $+ {}_n\mathrm{C}_{r+1}$ を証明してみよう。
公式
$n \geq 0$, $0 \leq r \leq n-1$ のとき,
${}_{n+1}\mathrm{C}_{r+1}$ $= {}_n\mathrm{C}_{r}$ $+ {}_n\mathrm{C}_{r+1}$
証明.
組合せ ${}_n\mathrm{C}_r$ の定義は
${}_n\mathrm{C}_r$ $\displaystyle =\frac{n!}{(n-r)! \cdot r!}$
であった. また,
${}_{n+1}\mathrm{C}_{r+1}$ $\displaystyle =\frac{(n+1)!}{(n-r)! \cdot (r+1)!}$,
${}_{n}\mathrm{C}_{r+1}$ $\displaystyle =\frac{n!}{(n-r-1)! \cdot (r+1)!}$
である.
${}_n\mathrm{C}_{r}$ $+ {}_n\mathrm{C}_{r+1}$
$\displaystyle =\frac{n!}{(n-r)! \cdot r!}$ $+\displaystyle \frac{n!}{(n-r-1)! \cdot (r+1)!}$
$\displaystyle =\frac{n!}{(n-r-1)! \cdot r!}$ $\displaystyle \cdot \left\{ \frac{1}{n-r} + \frac{1}{r+1} \right\}$
$\displaystyle =\frac{n!}{(n-r-1)! \cdot r!}$ $\displaystyle \cdot \frac{n+1}{(n-r)(r+1)}$
$\displaystyle =\frac{(n+1)!}{(n-r)! \cdot (r+1)!}$
となり, これは ${}_{n+1}\mathrm{C}_{r+1}$ である.
ゆえに, ${}_{n+1}\mathrm{C}_{r+1}$ $= {}_n\mathrm{C}_{r}$ $+ {}_n\mathrm{C}_{r+1}$ が成り立つ.
${}_6\mathrm{C}_{2}$ $\displaystyle =15$,
${}_6\mathrm{C}_{3}$ $\displaystyle =20$
であり, この和は $35$ である。
${}_7\mathrm{C}_{3}$ $\displaystyle =35$
なので, 公式は成立する。
