組み合わせの問題について

質問

組み合わせの証明について質問があります。

ΣnCk　（※kは偶数）
=ΣnCk　（※kは奇数）
=2^(n-1)

よろしくお願いします。

回答No.10

Tacosan · ベストアンサー

そう, 二項定理を使えば簡単.

帰納法でいくなら
i) n=1 のとき: 簡単なので省略.
ii) n=N で成り立つと仮定して
・N+1 が奇数なら (N+1)Ck = (N+1)C(N+1-k) より Σ(N+1)Ck (k: 奇数) = Σ(N+1)Ck (k: 偶数) なので偶数だけ証明することにして
Σ(N+1)Ck (k: 偶数) = (N+1)C0 + Σ(N+1)Ck (k: 2以上の偶数)
= NC0 + Σ[NC(k-1)+NCk] = ΣNCk (k: 奇数) + ΣNCk (k: 偶数) = 2^(N-1)+2^(N-1)
= 2^N.
・N+1 が偶数のとき, 奇数の k に対しては (N+1)Ck = NC(k-1) + NCk から簡単, 偶数の k については (N+1)C0 と (N+1)C(N+1) を切り離して上と同じようにする
でできます.

お礼

Tacosanさん

ご回答ありがとうございます。

具体的に書きだして、式の意味を理解する大切さを実感しました。

記号の移動だけにならないよう、
具体的に書きだす、ということを忘れずにがんばっていきます♪

回答No.9

Tacosan

仮定にしろ証明すべきものにしろ,
ΣmCk = 2^(m-1)
Σ(m+1)Ck = 2^m
の k の条件を書いてない. なんで書かないの?

あと, (m+1)Ck = mC(k-1) + mCk という性質が本当に m ≧ 1 かつ 0 ≦ k ≦ m を満たす整数 m, kで成り立ちますか? k=0 でも?

ところで, #7 への補足に書いてあることを, 例えば m=6 くらいでやってみましたか?

お礼

遅くなりまして申し訳ありません。

> ところで, #7 への補足に書いてあることを, 例えば m=6 くらいでやってみましたか?

やってみて、たくさんの間違いをみつけて、いままでやっていた証明も、最初から具体的に書き出して見直しました。

(m+1)Ck = mC(k-1) + mCk は m ≧ 1 かつ 1 ≦ k ≦ m を満たす整数 m, kでした。

この証明は二項定理を用いて、解くことができました（帰納法でどうやって特かは解決していませんが…）。

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

回答No.8

Tacosan

えぇと....

基本的には #7 への補足にある方法で証明できます. ただし, 落とし穴もちゃんと用意されています.

ちょっと確認してみましょうか.

まず, 「何を仮定して何を示すのか」をきちんと書いてください. なお, #5 でも書いたけど, 偶数と奇数を別々に証明する, つまり
「すべての (正の) n に対して ΣnCk　（※kは偶数）=2^(n-1)」
「すべての (正の) n に対して ΣnCk　（※kは奇数）=2^(n-1)」
を別々の命題として証明するのはやらない方がいいはず.

あと, その補足で使っているのは
(m+1)Ck = mC(k-1) + mCk
という性質ですね. では, これは任意の m と k で成り立つものですか? それとも, 何らかの条件がありますか?

お礼

> 「何を仮定して何を示すのか」

n=mのとき、
ΣmCk = 2^(m-1)

が成り立つと仮定して

Σ(m+1)Ck = 2^m

を示したいです。

> では, これは任意の m と k で成り立つものですか? それとも, 何らかの条件がありますか?

m ≧ 1 かつ 0 ≦ k ≦ m を満たす整数 m, kであれば成り立ちます。

回答No.7

Tacosan

うん, だから #2 で
「nCk の性質をどこまで知っているか知らんが」
って書いた.

知ってることを全部書き並べてみてください. その中に,
「n=mのとき成り立つと仮定して、
Σ(m+1)Ck
をどうやって変形すればいいか」
のヒントがあるかもしれませんよ.

お礼

うーん。

n=1
（※kは偶数）Σ1Ck=1C0=1　
（※kは奇数）Σ1Ck=1C1=1

n=2
（※kは偶数）Σ2Ck=2C0+2C2=1+1=2
（※kは奇数）Σ2Ck=2C1=2

n=3
（※kは偶数）Σ3Ck=3C0+3C2=4
（※kは奇数）Σ3Ck=3C1+3C3=4

n=4
（※kは偶数）Σ4Ck=4C0+4C2+4C4=8
（※kは奇数）Σ4Ck=4C1+4C3=8

n=5
（※kは偶数）Σ5Ck=5C0+5C2+5C4=16
（※kは奇数）Σ5Ck=5C1+5C3+5C5=16

n=6
（※kは偶数）Σ6Ck=6C0+6C2+6C4+6C6=32
（※kは奇数）Σ6Ck=6C1+6C3+6C5=32

うーん。
nからn+1のときに、2倍になっていることは証明することですし…。
奇数と偶数でCの数が交互に1つずつ増えていますが…。

n番目とn+1番目を結びつけることはできません。

補足

Σ(m+1)Ck = Σ{ mC(k-1) + mCk }
=ΣmC(k-1) + ΣmCk
= ??? + 2^{m-1}

やっぱり、???のところがダメです。わかりません。

回答No.6

Tacosan

#2 あたりでうすうす気になってはいたんだけど, そもそも証明すべき式の意味が理解できていないんじゃないだろうか....

小さな数値を入れて, 「何を証明すればいいのか」を説明してみてください.

お礼

>小さな数値を入れて
はい。

…勘違いしていたかもしれません。

n=1
（※kは偶数）Σ1Ck=1C0=1　
（※kは奇数）Σ1Ck=1C1=1

n=2
（※kは偶数）Σ2Ck=2C0+2C2=1+1=2
（※kは奇数）Σ2Ck=2C1=2

n=3
（※kは偶数）Σ3Ck=3C0+3C2=4
（※kは奇数）Σ3Ck=3C1+3C3=4

0は偶数でいいんですよね…？

> 「何を証明すればいいのか」を説明してみてください.
これを帰納法で証明します。

ですが、n=1のときは成り立つことはわかりましたが、

n=mのとき成り立つと仮定して、

Σ(m+1)Ck

をどうやって変形すればいいかわりません。

回答No.5

Tacosan

「m=1のとき」ってどういうこと?

あと, 偶数と奇数とで別々に証明しようとしない方がいいよ.

お礼

k=2mとしたときΣnC2m=2^(n-1)について調べたいので、m=1のときをしました。

> あと, 偶数と奇数とで別々に証明しようとしない方がいいよ.
別々にやらない方法が考えても思いつきません。

回答No.4

Tacosan

証明のストーリー書ける?

補足

偶数：
k=2mとする。
ΣnC2m=2^(n-1)
を示す。

m=1のとき
ΣnC2m=???

ここからがまずわかりません（奇数も同様です）。
Σの始まりはm=0だとしても終わりはわからないですよね？
そういう時のΣ計算の方法もわかりません。

回答No.3

Tacosan

それだけ聞かれても, なんともいいようがない.

どうしてその質問に至った (いいかえればどのように考えた結果としてそれが疑問点としてあがった) の?

お礼

Tacosanさん、すみません。
うまく言えませんが、なんとか汲み取っていただければと思います。

k=2l　（偶数）
k=2l+1　（奇数）

について、疑問というか、これでどうやったらいいかわからないというのは、

l=1,2,…について考えると、

k=2,4,6,…
k=3,5,7,…

となります。
数学的帰納法で証明するとき、k=1,2,3…の全てで成り立つ必要がありますが、
上の場合だと、すべてではなく、半分(偶数)、半分(奇数)なので、
数学的帰納法のk=1,2,3…の全てで成り立つという証明が
使うとしてもどのようにして使えばいいのかがわかりません。

回答No.2

Tacosan

nCk の性質をどこまで知っているか知らんが, 帰納法でもいいし母関数を使えば一瞬.

お礼

帰納法で証明する際、偶数奇数をどう扱えば良いのでしょうか。
k=2l　（偶数）
k=2l+1　（奇数）
で、証明すれば良いのでしょうか。

回答No.1

Tacosan

どこに質問があるのですか?

お礼

どのように証明すればよいかわかりません。