正しく証明・計算の結果が学術的に本当に正しいかどうかは保証できません…ご了承くださいm(__)m
学生の方であれば、疑問に思ったところなどは教授・助教授、その他周りの方に確認してくださいね。
もし、コメント等でご指摘いただければ有難いです。
【問題】${}_n C_r={}_{n-1} C_r+{}_{n-1} C_{r-1}$を証明せよ
${}_n C_r={}_{n-1} C_r+{}_{n-1} C_{r-1}$を証明せよ
回答
右辺$={}_{n-1} C_r+{}_{n-1} C_{r-1}$を左辺に変形することで証明します。
${}_n C_r$（組み合わせ）の公式より変形
まず、${}_n C_r$の公式より、$\displaystyle {}_{n} C_r = \frac{{}_{n} P_r}{r!}$なので、
$\displaystyle{}_{n-1} C_r+{}_{n-1} C_{r-1} = \frac{\color{red}{}_{n-1} P_r\color{black}}{r!}+\frac{\color{blue}{}_{n-1} P_{r-1}\color{black}}{(r-1)!}$・・・（１）
${}_n P_r$（順列）の公式より変形
次に、${}_n P_r$の公式より、$\displaystyle {}_{n} P_r = \frac{n!}{(n-r)!}$なので、（１）の赤、青はそれぞれ下記に変形できます。
$\displaystyle \color{red} {}_{n-1} P_r = \frac{(n-1)!}{\{(n-1)-r\}!}$$\displaystyle = \frac{(n-1)!}{(n-r-1)!}$・・・（２）
$\displaystyle \color{blue} {}_{n-1} P_{r-1} = \frac{(n-1)!}{\{(n-1)-(r-1)\}!} = $$\displaystyle \frac{(n-1)!}{(n-r)!}$・・・（３）
（１）に（２）（３）を代入します。
（１）$\displaystyle = \frac{\color{red}(n-1)!}{\color{red}(n-r-1)!\color{black}r!}+\frac{\color{blue}(n-1)!}{\color{blue}(n-r)!\color{black}(r-1)!}$・・・（４）
分母を合わせる
（４）の分母を合わせるために、$(n-r-1)!$を$(n-r)!$に、$(r-1)!$を$r!$に変形したいと思います。ここで、「$n!=n(n-1)!$を証明せよ」にて、$n!=n(n-1)!$となることが分かっていますのでそれを利用します。
$(n-r-1)!$を$(n-r)!$に変形
$n!=n(n-1)!$より、$(n-r)!$の場合は、$(n-r)!=(n-r)(n-r-1)!$となります。
つまり、$(n-r-1)!$に$(n-r)$を掛ければ$(n-r)!$に変形できます。よって、$(n-r-1)!$に対して$\displaystyle \frac{n-r}{n-r}$を掛けます。
$\displaystyle (n-r-1)!=\frac{(n-r)(n-r-1)!}{n-r}=$$\displaystyle \frac{(n-r)!}{n-r}$・・・（５）
$\displaystyle \frac{n-r}{n-r}$は$1$なので、どんな式・値に掛けても変化しませんので、問題ありません。
$(r-1)!$を$r!$に変形
$n!=n(n-1)!$より、$r!$の場合は、$r!=r(r-1)!$となります。
つまり、$(r-1)!$に$r$を掛ければ$r!$に変形できます。よって、$(r-1)!$に対して$\displaystyle \frac{r}{r}$を掛けます。
$\displaystyle (r-1)!=\frac{r(r-1)!}{r}=\frac{r!}{r}$・・・（６）
$\displaystyle \frac{r}{r}$は$1$なので、どんな式・値に掛けても変化しませんので、問題ありません。
（４）に（５）（６）を代入
（４）に（５）（６）を代入します。
（４）$\displaystyle = \frac{(n-1)!}{\color{red}(n-r-1)!\color{black}r!}+\frac{(n-1)!}{(n-r)!\color{blue}(r-1)!}$
$\displaystyle = \frac{\color{red}(n-r)\color{black}(n-1)!}{\color{red}(n-r)!\color{black}r!}+\frac{\color{blue}r\color{black}(n-1)!}{(n-r)!\color{blue}r!}$
$\displaystyle = \frac{(n-r)(n-1)!+r(n-1)!}{(n-r)!r!}$
$\displaystyle = \frac{\{(n-r)+r\}(n-1)!}{(n-r)!r!}$
$\displaystyle = \frac{n(n-1)!}{(n-r)!r!}$
「$n!=n(n-1)!$を証明せよ」より、$n!=n(n-1)!$なので、
$\displaystyle = \frac{n!}{(n-r)!r!}$・・・（７）
${}_n P_r$（順列）の公式より変形
（７）$\displaystyle = \frac{\color{red}n!}{\color{red}(n-r)\color{black}!r!}$
ここで、${}_n P_r$の公式より、$\displaystyle {}_{n} P_r = \frac{n!}{(n-r)!}$なので、上の赤部分を$\displaystyle {}_{n} P_r$に変形できます。
$\displaystyle = \frac{\color{red}{}_{n} P_r}{r!}$・・・（８）
${}_n C_r$（組み合わせ）の公式より変形
（８）$\displaystyle \color{red} = \frac{{}_{n} P_r}{r!}$
ここで、${}_n C_r$の公式より、$\displaystyle {}_{n} C_r = \frac{{}_{n} P_r}{r!}$なので、上の赤部分を$\displaystyle {}_{n} C_r$に変形できます。
$\displaystyle = \color{red}{}_{n} C_r$
右辺を左辺に変形できました。よって、${}_n C_r={}_{n-1} C_r+{}_{n-1} C_{r-1}$を証明できました。
Q.E.D.
スポンサーリンク
キーワード
気になる人は調べてみてね。
組合せ数学、階乗（$!$）、組み合わせ（${}_n C_r$）、順列（${}_n P_r$）、Q.E.D.
正しく証明・計算の結果が学術的に本当に正しいかどうかは保証できません…ご了承くださいm(__)m
学生の方であれば、疑問に思ったところなどは教授・助教授、その他周りの方に確認してくださいね。
もし、コメント等でご指摘いただければ有難いです。
