2項係数の上限

質問

こんにちは。興味本意で２項係数の上限を証明したいと思ってるのですが、うまくいきません。一応スターリングを使うのかなと思ったのですが、それでもうまくいきません。もしお分かりの方がいらっしゃいましたらご教授ください。証明するものは、

Binomial[n,k] <= 2^n /(Sqrt[Pi/x] * Sqrt[n] )です。

ここでBinomial[n,k]は２項係数を示し、
Sqrtは、平方根を示します。
Piは　Πです。

回答No.2

ringohatimitu · ベストアンサー

スターリングの公式；
Γ(x)=exp{ (x-1/2)log(x) - x + C + E(x) }
ここで
E(x)=∫_{0,∞} φ(u)e^{-xu}/u du
φ(u)={1/2-1/u+1/(e^u-1)}/u
C=1/2log(2π)
です。
これをBinomial[n,k]の定義式に代入します。冪の部分だけを書くと
(n+1/2)log(n+1) - (n+1) + C + E(1/(n+1))
- (n-k+1/2)log(n-k+1) + (n-k+1) - C - E(1/(n-k+1))
- (k+1/2)log(k+1) + (k+1) - C - E(1/(k+1))
＝ nlog(n+1) - { (n-k)log(n-k+1) + klog(k+1) }
+ 1/2log(n+1) - { 1/2log(n-k+1) + 1/2log(k+1) }
+ 1 - C + E(1/(n+1)) - E(1/(n-k+1)) - E(1/(k+1))
が得られます。
(n-k)log(n-k+1) + klog(k+1) ≧ nlog(n/2+1)　と
1/2log(n-k+1) + 1/2log(k+1) ≧ log(n/2+1) より
nlog(n+1) - { (n-k)log(n-k+1) + klog(k+1) }
+ 1/2log(n+1) - { 1/2log(n-k+1) + 1/2log(k+1) }
+ 1 - C + E(1/(n+1)) - E(1/(n-k+1)) - E(1/(k+1))
≦ nlog(n+1) - nlog(n/2+1)
+ 1/2log(n+1) - log(n/2+1) + 1 - C
+ E(1/(n+1)) - E(1/(n-k+1)) - E(1/(k+1))
＝ nlog{(n+1)/(n+2)} + nlog2
+ 1/2log(n+1) - log(n+2) + log2 + 1 - C
+ E(1/(n+1)) - E(1/(n-k+1)) - E(1/(k+1))
≦ nlog{(n+1)/(n+2)} + nlog2
- 1/2log(n+2) + log2 + 1 - C
+ E(1/(n+1)) - E(1/(n-k+1)) - E(1/(k+1))
主となる項はnlog2と-1/2log(n+2)とCとlog2で、これらをexpで計算すれば2^n/√{(π/2)(n+2)}となります。あとは誤差項の評価ですがこれは最初のEの定義に従って計算すればおそらく誤差が√{(n+2)/n}に納まると思うので求める評価が得られます。ｎについての漸近的評価を知りたいときは誤差項がｎに関して一様に０に収束することから十分大きなｎに対して求める不等式が成り立つことはすぐわかりますがすべてのｎに対して示すときは誤差項をある程度正確に計算しなければならないので少々面倒ですね。

回答No.1

ringohatimitu

右辺のｘは何を表していますか？それと２項係数とはCombinationのことでいいですか？

お礼

すみません。言葉足らずでした。右辺のxは、２の間違いです。ですのです、Sqrt[Pi/2]となります。２項係数はCombinationのことで大丈夫です。