17/09/03 13:45:23.58 bEBpcPP5.net
nCr＋nC(r＋1)＝(n＋1)C(r＋1)の証明
(計算ではミスが発生するから論理で示してみせた)
組合せの定義と nC(r+1) とに着目すると、n、r は n≧r+1、r≧0 を満たすような非負整数の値を取る変数と仮定してよい。
1)：n＝1 のとき。このとき、nC(r+1) に着目すると、組合せの定義からrが取り得る値は r＝0 に限る。
定義から 1個の中から重複を許さずに0個を選び組合せる場合の数 1C0 と
同じ1個から重複を許さずに 0+1＝1 個を選び組合せる場合の数 1C1 は両方共に1通り。
また、定義から、合計 1+1＝2 個の中から重複を許さず 0+(0+1)＝1 個選び組合せる場合の数は 2C1＝2 通り。
故に、1C0＋1C1＝2C1 である。
2)：n≧2 のとき。2以上の整数nを任意に取る。n＞r≧0 なる非負整数rを任意に取る。
2-1)：r＝0 のとき。1)と同様に考えて何れも重複を許さない組合せ nC0、nC1、(n+1)C1 を
それぞれその順に求めると 1、n、n+1 となるから、nC0＋nC1＝(n+1)C1 である。