二項係数の証明

C[n,k-1]+C[n,k]=C[n+1,k]の証明ってどのようにやるのでしょうか。
わかりやすく教えていただけると幸いです。

No.1 回答者： banakona 回答日時： 2009/05/22 18:02

では「わかりやすく」。

ｎ＋１個の内の、「ある１個」に着目して、それが含まれるものと含まれないものに、C[n+1,k]を分けます。

含まれるものは、残りのｎ個からｋ－１個を選ぶ個数なので、C[n,k-1]

含まれないものは、残りのｎ個からｋ個を選ぶ個数なので、C[n,k]

よって、これらを足せばC[n+1,k]になる（ハズです）。

No.2 回答者： proto 回答日時： 2009/05/22 18:38

　　C[n,k] = n!/(k!*(n-k)!)

ですね。
同様に、
　　C[n,k-1] = n!/((k-1)!*(n-k+1)!)
　　C[n+1,k] = (n+1)!/(k!*(n-k+1)!)
ですね。

このように左辺を分数の形で書いてから、分母をうまく揃えて通分するように変形していけば簡単に証明できると思います。

No.3 回答者： arrysthmia 回答日時： 2009/05/22 18:42

では、私は「証明」のほうを…

C[n,k] の定義は、= n ! /｛ k ! (n-k) ! ｝ です。
この定義に沿って、質問の式を書き換え、
左辺を k ! (n-k+1) ! で通分してみましょう。
左辺を計算整理すれば、
右辺と同じ式が現れます。

No.4 回答者： arrysthmia 回答日時： 2009/05/22 20:22

失礼。

かぶったようなので、別証を…

二項定理を二項係数の定義にしてしまう立場もあります。
その場合、階乗を使った表示は、定義でなく定理になります。
その立場では…

x(x+1)~n + (x+1)~n = (x+1)~(n+1)
の両辺で、x~k の係数を比較すれば判ります。