 | # 今頃回答が付いても無意味かもしれませんが・・・。
べき乗演算子^は四則演算より優先度が高いものとします。
組み合わせの数nCrをC(n, r)と表すこととします。
nを2以上の自然数として、
C(2n, n) = ((2n)!)/(n!)((2n-n)!)
= {(2n)(2n-1)(2n-2)・・・(2n-(n-1))}/{(n)(n-1)(n-2)・・・(n-(n-1))}
= {(2n)(2n-1)(2n-2)・・・(n+1)}/{(n)(n-1)(n-2)・・・(1)}
n = 2のとき、C(2*2, 2) = {4*3}/{2*1} = 6 かつ 2^(2*2-1) = 8 なので、
C(2n, n) < 2^(2n-1)という題意は成立します。
kを2以上の自然数として、n = kのときにC(2k, k) < 2^(2k-1)が成立すると仮定します。
C(2k, k) = {(2k)(2k-1)(2k-2)・・・(k+1)}/{(k)(k-1)(k-2)・・・(1)}です。
すると、n = k+1の場合、
C(2(k+1), k+1) = {(2(k+1))(2(k+1)-1)(2(k+1)-2)・・・((k+1)+1)}/{(k+1)((k+1)-1)((k+1)-2)・・・(1)}
= {(2k+2)(2k+1)(2k)(2k-1)(2k-2)・・・(k+2)}/{(k+1)(k)(k-1)(k-2)・・・(1)}
= {{(2k+2)(2k+1)/(k+1)}/{(k+1)}}C(2k, k)
ここで、
{(2k+2)(2k+1)/(k+1)}/{(k+1)} = {(2k+2)/(k+1)}{(2k+1)/(k+1)} = 2{2-1/(k+1)} < 2^2
ですから、
C(2(k+1), k+1) < (2^2)C(2k, k) < 2^(2+(2k-1)) = 2^(2(k+1)-1)
となり、n = k+1でも題意は成立します。
以上から数学的帰納法により、nを2以上の自然数としてC(2n, n) < 2^(2n-1)が成立すると言えます。
|
このトピックをツリーで一括表示