帰納法で行ける？

質問

q=90330絡みの質問です。

　　　　Σ(k=0~n) k * nCk * (N-n)C(n-k) / NCn　= n^2 / N
が経験的に正しそうなのですが、証明の仕方がわかりません。
数学的帰納法でいけるかと頑張ってはみてるのですが上手くいきません。

誰か証明してください。

式の背景的意味合いについては
http://oshiete1.goo.ne.jp/kotaeru.php3?q=90330
をご参照下さい。

回答No.1

stomachman · ベストアンサー

F(N,n)=Σ{k=0～n} nCk (N-n)C(n-k) /NCn
とします。
∀N ∀n F(N,n) =1
であることは証明できそうかな？確率である以上はこうなってなきゃおかしいですよね。
これが示せたら、
E(N,n)=Σ{k=0～n}k nCk (N-n)C(n-k) /NCn
が
E(N,n)=(n^2)/N
となることは以下のようにやれば良いでしょう。
STEP1
∀N（E(N,0)=0)
∵E(N,0)=0 0C0 NC0 /NC0 = 0
STEP2
∀N (E(N,n)=(n^2)/N)
であると仮定するとき、
∀N （E(N+1,n+1)=((n+1)^2)/(N+1)）
である。
∵E(N+1,n+1)=Σ{k=0～n+1}k (n+1)Ck (N-n)C(n+1-k) /(N+1)C(n+1)
=(1/(N+1)!)((n+1)! (N-n)!)^2Σ{k=1～n+1}k /[(n+1-k)!^2 k! (N+1-k)!]
=[(n+1)^2/(N+1)](1/N!)(n! (N-n)!)^2Σ{k'=0～n}1/[(n-k'))!^2 k'! (N-k')!]
=[(n+1)^2/(N+1)]F(N,n)

かくて、F(N,n)=1を示す問題に帰着。いつもイー加減ですいませんねえ。

お礼

そうか、E(N,n+1)じゃなくてE(N+1,n+1)を考えれば良かったんですね。
ところでE(N+1,n+1)を証明するのにE(N,n)を使ってませんよね。ってことは帰納法ではないですね。
F(N,n) = 1については何だか上手く証明できないのですが、「確率だから」という大義名分の下に自明としまっていいんじゃないでしょうか？。
「全ての事象の確率の和は１となる」みたいな定理、ありませんかね？
（というか、もう２項係数はもう見たくもないというのが本音ですが。(笑)）
後は納得です。ちっともいい加減じゃないですよ。

おかげで心のもやもやが晴れました。ありがとうございました。

回答No.2

stomachman

帰納法だと仰るから、つい吊られちゃいましたが、言われてみれば帰納法不要ですね、これ。
ぅぁやっぱり、イー加減ですいませんでした。

お礼

いやいや、とんでもない。
帰納法は勝手に僕の方が騒いでいただけの話で、
解けた事に意義があるんです。

１人で２日間くらい悶々と苦しんでいたので助かりました。
ありがとうございました。