陽表式の数学的帰納法による証明

数三角形の細胞_nC_rの陽表式は
_nC_r
＝n!/r!(n－r)!
＝n(n－1)(n－2)･ ･･･ ･(n－r＋2)(n－r＋1)/1･2･3･ ･･･ ･(r－1)･r
になった。
これを数学的帰納法で証明しておこう。
第二補題だけをみる。

陽表式がnについて成り立っていると仮定する。
すなわち、一つの細胞とそれに隣接する細胞について、
_nC_r＝n(n－1)(n－2)･ ･･･ ･(n－r＋2)(n－r＋1)/1･2･3･ ･･･ ･(r－1)･r
と
_nC_r－1＝n(n－1)(n－2)･ ･･･ ･(n－r＋2)/1･2･3･ ･･･ ･(r－1)
を仮定する。

これら二つの等式を加えると、
_nC_r＋_nC_r－1
＝n(n－1)(n－2)･ ･･･ ･(n－r＋2)/1･2･3･ ･･･ ･(r－1)・[(n－r＋1)/r ＋ 1]
＝n(n－1)(n－2)･ ･･･ ･(n－r＋2)/1･2･3･ ･･･ ･(r－1)・(n＋1)/r
＝(n＋1)n(n－1)(n－2)･ ･･･ ･(n－r＋2)/1･2･3･ ･･･ ･(r－1)･r　　……(p)
となる。
ここで最後の式(p)
(n＋1)n(n－1)(n－2)･ ･･･ ･(n－r＋2)/1･2･3･ ･･･ ･(r－1)･r
は
n(n－1)(n－2)･ ･･･ ･(n－r＋1)/1･2･3･ ･･･ ･r＝_nC_r
と対照してかけば、
＝(n＋1)((n＋1)－1)((n＋1)－2)･ ･･･ ･((n＋1)－r＋1)/1･2･3･ ･･･ ･r
＝_n＋1C_r
である。
したがって、(p)は、
回帰公式_n＋1C_r＝_nC_r＋_nC_r－1を満たし、
陽表式_nC_r＝n!/r!(n－r)!が
(n＋1)に対しても成立していることを示している。
これで証明は終わった。

（注）『数学の問題の発見的解き方1』第3章参照、式の変形は記号(ⁿ_r)を_nC_rに置き換えて引用した。