二項係数 \(_n C_r\) は, 次の漸化式が成り立つことを確かめなさい.
\[_n C_r=_{n-1} C_r +_{n-1} C_{r-1}\]ただし, \(1\leqq r\leqq n\) とします.


参考:場合の数
(右辺)=(左辺)を示せばよい.
(右辺) \(=_{n-1} C_r +_{n-1} C_{r-1}\)
\(=\dfrac{(n-1)!}{r!(n-r-1)!}+\dfrac{(n-1)!}{(r-1)!(n-r)!}\)
\(=\dfrac{(n-1)!}{r!(n-r)!}\{(n-r)+r\}\)
\(=\dfrac{(n-1)!n}{r!(n-r)!}\)
\(=_n C_r=\) (左辺)・・・(答)

(別解)
特定の \(a\) を含むものと含まないものとに場合分けして考えるとよい.
(i) \(a\) を含む場合
\(a\) 以外の \(n-1\) 個から \(r-1\) 個をとって \(a\) を合わせた総数で \(_{n-1} C _{r-1}\) となる.

(ii) \(a\) を含まない場合
\(a\) 以外の \(n-1\) 個から \(r\) 個をとった総数で \(_{n-1} C _r\) となる.

(i)+(ii)より
\(_n C_r=_{n-1} C_r +_{n-1} C_{r-1}\)・・・(答)