1. まえがき
数学的帰納法にはいくつかのバリエーションがあるが、特に説明も無く自明と思ってい
た。ある所で疑問が投げられていたので改めて考えてみた。
2. 説明
2.1 基本形
数学的帰納法はよく知られたように、自然数nについての命題をP(n)とすると、「P(1)
の真を証明し、P(n)の真を仮定して、P(n+1)が真となることを証明すると、n≧1 につ
いてP(n)が真となる。」ことである。
2.2 バリエーション1
1以外から始める。
ほぼ自明だが、命題P(n)を使って、整数mを使って、新たな命題をQ(n)=P(n+m-1)とす
る。Q(n)に基本形を使えば、P(n)について、n≧mでP(n)の真を証明できる。
2.3 バリエーション2
P(1), P(2)の真を証明し、P(n),P(n+1)の真を仮定してP(n+2)の真を証明できれば、n≧1
についてP(n)は真となる。
Q(n)=P(n)かつP(n+1) とする。するとQ(1)つまり、P(1)かつP(2)を証明し、Q(n)つまり、
P(n),P(n+1)を仮定して、Q(n+1)つまり、P(n+1),P(n+2)を証明すれば、n≧1 でQ(n)つま
り、P(n),P(n+1)の真が言える。ここで、最後のP(n+1),P(n+2)の証明について、P(n+1)
は仮定に含まれているから、P(n+2)だけを証明すればよい。
2.4 バリエーション3
P(1)の真を証明し、m≦nのすべての自然数mについて、P(m)の真を仮定したとき、
P(n+1)の真を証明できれば、n≧1 についてP(n)は真となる。
この場合も、Q(n)=P(1)かつP(2)かつ・・・かつP(n)とすればよい。Q(n+1)の証明は
Q(n)の仮定がなされているので、P(n+1)の真のみ証明すればよい。
2.5 特殊な例
AM-GM不等式の証明に用いられていた方法で
(1) P(1) を証明
(2) P(n) → P(2n)を証明
(3) P(n) → P(n-1) を証明
するものである。P(n)の仮定により、P(2n)が証明されるが、(3)により、P(2n-1),
P(2n-2),・・・,P(n+1)が順次証明される。つまり、(2)(3)を合わせると P(n) → P(n+1)
が証明されたことになり、普通の帰納法と同じになる。
3. 例
3.1 チェビシェフの多項式（基本形）
命題：sin(nθ)はcosθの(n-1)次多項式とsinθの積で現せる。
証明：n=1は明らか。nのときの成立を仮定すると、公式
sin(n+1)θ=sin(nθ)cosθ+cos(nθ)sinθ とつぎの、3.2項の命題を使うと n+1 で
も成立つ。
3.2 チェビシェフの多項式（バリエーション2）
命題：cos(nθ)はcosθのn次多項式で現せる。
証明：n=1は明らか。n=2のとき、cos2θ=2cos²θ-1 から成立。公式
cosx+cosy=2cos{(x+y)/2}cos{(x-y)/2} においで、x=(n+2)θ、y=nθとする
と cos(n+2)θ=2cos{(n+1)θ}cosθ−cos(nθ) が成立する。したがって、n、n+1
で命題の成立を仮定すると n+2のときも成立する。
このパターンは、フィボナッチ数列の一般項の証明のように、３項間漸化式が与え
られている場合に使われる。
3.3 チェビシェフの多項式2（基本形の応用）
以下のように、3.1、と3.2項を同時に証明する方法もある。
n=1 のときは、cosθとsinθで自明。nのとき、命題の成立を仮定し、3.1、3.2項の結
果を使うと、n+1 で
cos((n+1)θ)=cos(nθ)cosθ - sin(nθ)sinθ
={cosθのn次式}cosθ-{cosθの(n-1)次式}sin²θ
={cosθの(n+1)次式}-{cosθの(n+1)次式}={cosθの(n+1)次式}
だから、n+1 のとき、3.2項が成立。
つぎに、
sin((n+1)θ)=sin(nθ)cosθ + cos(nθ)sinθ
={cosθ の(n-1)次式}sinθcosθ-{cosθ の n次式 }sinθ
={cosθ の n 次式 }sinθ.
だから、n+1 のときに、3.1項が成立。
以上
最新の画像［もっと見る］
