数学的帰納法

    更新日時 2021/03/12

    連続するn個の整数の積と二項係数

    整数論の有名な公式:

    連続する nn 個の整数の積は n!n! の倍数である。

    上記の公式について,3通りの証明を紹介します。

    → 連続するn個の整数の積と二項係数

    ライプニッツの公式の証明と二項定理

    複数の関数の積の微分を効率よく行う公式

    f,g,hf, g, hxx の関数とする。関数の積は以下のように微分できる:

    (i) (fg)=fg+fg(fg)'=f'g+fg'

    (ii) (fg)=fg+2fg+fg(fg)^{\prime\prime}=f^{\prime\prime}g+2f'g'+fg^{\prime\prime}

    (iii) (fgh)=fgh+fgh+fgh(fgh)'=f'gh+fg'h+fgh'

    (i)は数Ⅲの教科書にも載っている有名な公式です。公式(ii),(iii)も実戦で使用することがあるので覚えておくと時短になります。

    公式や定理を見た時になんでも拡張しようと考えるのはよい習慣ですが,(i)を拡張しようと思ったときに2つの方法が考えられます。

    1.微分の回数を増やす(→公式(ii),より一般的には二項定理)

    2.積を取る関数の数を増やす(→公式(iii)より一般的には多項定理)

    → ライプニッツの公式の証明と二項定理

    イェンゼンの不等式の3通りの証明

    イェンゼンの不等式(Jensen,凸関数の不等式)

    f(x)f(x) が凸関数のとき,

    任意の λi0,xi(i=1,,n),i=1nλi=1\lambda_i\geq 0,\:x_i\:(i=1,\cdots,n),\:\displaystyle\sum_{i=1}^n\lambda_i=1

    に対して,

    i=1nλif(xi)f(i=1nλixi){\displaystyle\sum_{i=1}^{n}\lambda_if(x_i)}\geq f({\displaystyle\sum_{i=1}^{n}\lambda_ix_i})

    特に n=2,3n=2, 3 の場合が頻繁に用いられます:

    n=2:λ1,λ20,λ1+λ2=1n=2:\lambda_1,\lambda_2\geq 0, \lambda_1+\lambda_2=1 のとき

    λ1f(x1)+λ2f(x2)f(λ1x1+λ2x2)\lambda_1f(x_1)+\lambda_2f(x_2)\geq f(\lambda_1x_1+\lambda_2x_2)

    n=3:λ1,λ2,λ30,λ1+λ2+λ3=1n=3:\lambda_1,\lambda_2, \lambda_3\geq 0,\lambda_1+\lambda_2+\lambda_3=1 のとき λ1f(x1)+λ2f(x2)+λ3f(x3)f(λ1x1+λ2x2+λ3x3)\lambda_1f(x_1)+\lambda_2f(x_2)+\lambda_3f(x_3)\geq f(\lambda_1x_1+\lambda_2x_2+\lambda_3x_3)

    → イェンゼンの不等式の3通りの証明

    包除原理の2通りの証明

    包除原理:

    AB=A+BAB|A\cup B|=|A|+|B|-|A\cap B|

    ABC=A+B+CABBCCA+ABC|A\cup B\cup C|\\ =|A|+|B|+|C|\\ -|A\cap B|-|B\cap C|-|C\cap A|\\ +|A\cap B\cap C|

    より一般に,

    A1A2An|A_1\cup A_2\cup\cdots\cup A_n|

    =k=1n(1)k1=\displaystyle\sum_{k=1}^n(-1)^{k-1}kk個の「かつ」の総和)

    =iAii<jAiAj=\displaystyle\sum_{i}|A_i|-\sum_{i < j}|A_i\cap A_j|

    +i<j<kAiAjAk+\sum_{i < j < k}|A_i\cap A_j\cap A_k|

    +(1)n1A1An-\cdots +(-1)^{n-1}|A_1\cap\cdots\cap A_n|

    上の2つの式は教科書でもおなじみの公式ですね。しかし,初めて包除原理を知った人にとっては最後の式は意味不明でしょう。

    この記事では包除原理の意味と,2通りの証明を紹介します。

    証明1.意味を考えつつ二項定理を用いる方法

    証明2.数学的帰納法を用いてゴリゴリ計算していく方法

    → 包除原理の2通りの証明

    ヴァンデルモンドの畳み込みの3通りの証明

    ヴァンデルモンドの畳み込み:

    以下の恒等式が成立する:

    k=0npCkqCnk=p+qCn\displaystyle\sum_{k=0}^n{}_p\mathrm{C}_k\cdot {}_q\mathrm{C}_{n-k}={}_{p+q}\mathrm{C}_n

    ただし,p<kp < k のとき pCk=0{}_p\mathrm{C}_k=0 と約束する。

    この恒等式はヴァンデルモンドの畳み込み(Vandermonde’s convolution),ヴァンデルモンドの恒等式(Vandermonde’s identity)などと呼ばれる有名な恒等式です。

    • 某有名予備校の模試でそのまんま出題されたことがあります。
    • 2014千葉大後期数学科で似たような問題が出題されたらしいです。

    二項係数の関係式を導く問題のよい例となっているのでおさえておきましょう。

    → ヴァンデルモンドの畳み込みの3通りの証明

    オイラーグラフの定理とその証明

    一筆書きの条件:

    連結なグラフにおいて,

    オイラーグラフ⇔全ての頂点の次数が偶数

    準オイラーグラフ⇔次数が奇数であるものがちょうど2つ

    → オイラーグラフの定理とその証明

    フィボナッチ数列の一般項と数学的帰納法

    フィボナッチ数列とは,1,1,2,3,5,8,13,21 のように,各項が「前の2つを足した値」になるような数列のこと。

    この記事では, フィボナッチ数列の意味 を解説した後, フィボナッチ数列の美しい性質を3つ 紹介します。

    → フィボナッチ数列の一般項と数学的帰納法

    無限降下法の整数問題への応用例

    このページでは,無限降下法について解説します。

    • 無限降下法とは何か?

    • 無限降下法の簡単な応用例:3\sqrt{3} が無理数であることの証明

    • 無限降下法の難しい応用例:フェルマーの最終定理の n=4n=4

    → 無限降下法の整数問題への応用例