数学ナビゲーター掲示板

HOME HELP 新規作成 新着記事 ツリー表示 スレッド表示 トピック表示 発言ランク ファイル一覧 検索 過去ログ

[ 最新記事及び返信フォームをトピックトップへ ]

■52213 / inTopicNo.1)  二項係数2nCn
  
□投稿者/ 二項係数 一般人(1回)-(2023/06/01(Thu) 23:20:51)
    nが2以上のとき
    2nCn<2^(2n-1)
    の証明教えて下さい
引用返信/返信 [メール受信/OFF] 削除キー/
■52310 / inTopicNo.2)  Re[1]: 二項係数2nCn
□投稿者/ WIZ 一般人(3回)-(2023/09/11(Mon) 18:10:06)
    # 今頃回答が付いても無意味かもしれませんが・・・。

    べき乗演算子^は四則演算より優先度が高いものとします。
    組み合わせの数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)が成立すると言えます。
引用返信/返信 [メール受信/OFF] 削除キー/



トピック内ページ移動 / << 0 >>

このトピックに書きこむ

Mode/  Pass/

HOME HELP 新規作成 新着記事 ツリー表示 スレッド表示 トピック表示 発言ランク ファイル一覧 検索 過去ログ

- Child Tree -
Edit By 数学ナビゲーター