2014/04/04

数学的帰納法のパターンまとめ

分野: まとめ

入試問題や数学オリンピックで頻出の数学的帰納法を用いた証明方法の5つのパターンをまとめてみました。この5パターンを知っていれば数学的帰納法の応用の幅が広がります!

特に数学オリンピックなどの難問ではパターン3,4を知らないと厳しいものもある(最難関大学でもまれに出題されます)のでオススメです。

1:数学的帰納法の基本パターン

数学的帰納法の基本パターンは $n=1$ の場合を証明した後,$n=k-1$ の場合を仮定して,$n=k$ の場合にも成り立つことを証明するパターンです。「ドミノ倒し」のイメージです。

例(整数問題):連続するn個の整数の積と二項係数の3番目の証明
例(集合):包除原理の2通りの証明の2番目の証明
例(不等式):イェンゼンの不等式の3通りの証明の1番目の証明
例(微分):ライプニッツの公式の証明と二項定理

2:一つ前だけでなく二つ前も仮定するパターン

$n=1, 2$ の場合を証明した後,$n=k-2, k-1$ の場合を仮定して,$n=k$ の場合にも成り立つことを証明します。3つ以上仮定することもあります。

フィボナッチ数列の一般項と数学的帰納法の中盤,ビネの公式の証明

3:前の項を全て仮定するパターン

先ほどのパターン2をさらに一般化したもので,数学オリンピックの離散数学などの難問ではこのパターンが多いです。 $n=1$ の場合を証明した後,$n\leq k-1$ を満たす全ての自然数 $n$ に対して成り立つと仮定して,$n=k$ の場合にも成り立つことを証明します。

4:後ろ向き帰納法(無限降下法)

$n=k$ のときを仮定して $n=k-1$ の場合を証明します。背理法と組み合わせて使うことが多く,無限降下法と呼ばれます。

5:多変数の数学的帰納法

レアなケースです。複数の自然数のペア$(m, n)$ 全てに関して成立すること示します。原点から離れる方向にドミノ倒しをしていくイメージです。

数学的帰納法は素晴らしい

数学的帰納法は整数問題,数列,組み合わせ(離散数学),恒等式の証明,などなど様々な分野の証明問題に使える非常に強力な方法です。自然数 $n$ が登場する証明問題の多くは数学的帰納法で解決できます。

数学的帰納法を用いた証明と,数学的帰納法を用いずに直接証明する方法を比べると,一般的に以下のような特徴が見受けられます:

数学的帰納法:機械的な計算で証明できることが多い,発想力がいらない
直接証明する方法:発想力が必要な場合が多い,よりエレガントな解答になりやすい

もちろん,数学オリンピックの問題など,数学的帰納法を用いた上でも発想力が必要になる問題もありますが,自然数 $n$ が含まれる証明問題を見たらとりあえず,どの分野でも数学的帰納法を連想しましょう。

数学的帰納法を使えば全ての人がハゲであることを証明できます
分野: まとめ