不等式への招待 第3章

このエントリーをはてなブックマークに追加
333132人目の素数さん
http://science6.2ch.net/test/read.cgi/math/1209732803/79
から転載

nPk < (k! 2^n)/√n が成り立つことを示せ
ただしnPkは順列の個数を意味する
334132人目の素数さん:2008/05/31(土) 20:35:13
>>333

nPk /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) にすると、間単に出る所がミソ。