- 334 名前：１３２人目の素数さん mailto:sage [2008/05/31(土) 20:35:13 ]
- >>333
nＰk /k! = C(n,k) とおくと、問題の式は C(n,k) < (2^n)/√n,
C(n,k) = C(n,k-1)*((n+1-k)/k),
より、左辺は k=[n/2] に向かって単調に増加する。
∴ C(n,k) ≦ C(n,[n/2]),
〔補題〕
C(n,[n/2]) ≦ (2^n)/√(n+2),
等号成立は n=2 のとき。
(略証)
nについての帰納法による。
n=1,2 のとき成立。
nが偶数のとき、n=2m,
C(2m,m) = 4{(m -1/2)/m}･C(2m-2,m-1) < 4√{2m/(2m+2)}･C(2m-2,m-1),
C(2m,m){1/[2^(2m)]}√(2m+2) は単調減少。
C(2m,m) ≦ {2^(2m)}/√(2m+2),
nが奇数のとき、
C(2m-1,m) = (1/2)C(2m,m) < {2^(2m-1)}/√(2m+2), (終)
※ 分母を √(n+2) にすると、間単に出る所がミソ。
