二項係数の和で、二項定理を使わない証明

∑ [k = 0 to n] C(n, k) = 2^n
※ C(n, k) = n個の異なるものからk個の異なるものを選び出す組合せ

よくあるこの等式は、通常二項定理を使って示しますが、二項定理を使わず、直接計算等によって示すことは可能でしょうか。

よろしくお願いします。

No.3 回答者： majimelon37 回答日時： 2020/02/14 02:36

二項係数をパスカルの三角形を使って表すと、図のようになる。

パスカルの三角形の2行目の合計は　１＋１＝２
３行目の二項係数の合計は　　　１＋２＋１＝４
４行目の二項係数の合計は　　１＋３＋３＋１＝８
質問は、これらの式が成立して、ｎ行目の合計が２^ｎとなることを証明せよです。
パスカルの三角形において、二項係数は、第ｎ行の隣り合う二つの二項係数を、矢印に従って集めてたした数が第ｎ＋１行の二項係数として作り出される。
そこで、第ｎ行から左下に向いた矢印↙に従って集めた数の合計と第ｎ行から右下に向いた矢印↘に従って集めた数の合計をたすと、第ｎ＋１行の二項係数の合計になる。
第ｎ行から左下に向いた矢印↙に従って集めた数の合計は２^ｎである。
第ｎ行から右下に向いた矢印↘に従って集めた数の合計は２^ｎである。
よって第ｎ＋１行の二項係数の合計は２^(ｎ＋１)である。
この証明を数式を使って行ったのがNo.1回答です。

この回答へのお礼

ありがとうございました。

お礼日時：2020/02/14 17:55

No.2 回答者： endlessriver 回答日時： 2020/02/11 15:42

同じく直接計算ではないけど、微分を使って。

(1+x)ⁿ をマクローリン展開して
(1+x)ⁿ=Σf^(k)(0)/k! x^k=Σ(n!/(n-k!))/k! x^k=ΣnCk x^k, f⁽ⁿ⁺¹⁾(x)=0
x=1 として。

２項展開みたいけど。

この回答へのお礼

ありがとうございました。
微分を使った手法は有効ですね。

お礼日時：2020/02/14 17:55

No.1 ベストアンサー 回答者： ありものがたり 回答日時： 2020/02/11 14:39

二項定理を使うのが、二項係数の定義にもとづく直接計算だと思うがなあ。

他の計算というなら、n についての数学的帰納法はどうか。

パスカルの三角形
C(n,k) + C(n,k+1) = n!/( k! (n-k)! ) + n!/( (k+1)! (n-(k+1))! )
= { n!/( (k+1)! (n-k)! ) }{ (k+1) + (n-k) }
= { n!/( (k+1)! (n-k)! ) }(n+1)
= (n+1)!/( (k+1)! (n-k)! )
= C(n+1,k+1).
を k = 0,1,2,...,n-1 で Σして
∑ [k = 0 to n-1] C(n+1, k+1) = ∑ [k = 0 to n-1] C(n,k) + ∑ [k = 0 to n-1] C(n,k+1)
= { ∑ [k = 0 to n] C(n,k) - C(n,n) } + { ∑ [k = 0 to n] C(n,k+1) - C(n,0) }
= { 2^n - 1 } + { 2^n - 1 }
= 2^(n+1) - 2.
これを使って
∑ [k = 0 to n+1] C(n+1, k) = ∑ [r = -1 to n] C(n+1, r+1)
= ∑ [r = 0 to n-1] C(n+1, r+1) + C(n+1,0) + C(n+1,n+1)
= { 2^(n+1) - 2} + 1 + 1
= 2^(n+1).

これに n = １ のときの
∑ [k = 0 to １] C(１, k) = C(1,0) + C(1,1) = 1 + 1 = 2^1
を添えれば、数学的帰納法が完成する。

この回答へのお礼

ありがとうございました。
まずは直接計算の定義を考えるべきだったかもしれません。
∑ [k = 1 to n] k = n は直接計算していないように思えます。

お礼日時：2020/02/14 17:30