数学的帰納法
出典: フリー百科事典『ウィキペディア（Wikipedia）』
数学的帰納法（すうがくてききのうほう）とは、有限回の議論で可算無限個の対象に対する命題を証明するための数学の論法である。次のような手順で自然数全体に関する命題 P(n) (n∈N) が真であることを証明する論法である。
-
- P(0) は真である。
- 任意の自然数 k に対し，P(k) が真であれば，P(k+1) も真である。
- よって任意の自然数 n について P(n) は真である。
イメージとしては、2 により次々と次の命題の正しさが伝播されていくことになる。つまり、1 によりまず P(0) は正しく、P(0) と 2 により P(1) は正しく、P(1) と 2 により P(2) は正しく、以下これが果てしなく続いていく。このことによって任意の自然数 n について P(n) が正しいことが保証される。
なお、数学的「帰納法」という名前がつけられているが、数学的帰納法の解法プロセス自体は帰納法ではなく演繹法である。先に述べた、「2 により次々と次の命題の正しさが伝播されてい」った結果証明されていく様子が帰納っぽいからつけられたにすぎない。
目次 |
[編集] 等価なもの
数学的帰納法は自然数を特徴づけるものの一つで、以下の命題と等価。
- ペアノの自然数論の公理の一つである次の趣旨の命題：自然数は1,2,3,...しかない。
- 自然数の任意の空でない集合Sに対し、Sには最小元が存在する。
[編集] 例
任意の自然数 n について、0 + 1 + 2 + ... + n = n(n+1)/2 であることを証明する。自然数 k によって定まる命題 P(k) を 「0 + 1 + ... + k = k(k+1)/2である」 とすればよい。
まず、P(0)、つまり「0 = 0(0+1)/2」は正しい。
つぎに、任意の自然数 k をとる。今、P(k) が正しいと仮定すると P(k+1) も正しい。実際、P(k) より
となり、更にこれは
となるので P(k+1) が成立した。
以上から、数学的帰納法により、任意の自然数 n について命題 P(n) が成立する。
[編集] バリエーション
数学的帰納法には次のようなバリエーションもある。場合によってはこちらを用いた方が議論が容易になる。これらのバリエーションはいずれも同値であるので、本質的には上と変わらない。
[編集] 背理法を組み合わせたもの1
-
- P(0) は真である。
- P(k+1) が偽であれば、P(k) も偽である。
- よってP(k) が偽であるkは存在せず、したがって任意の自然数 n について P(n) は真である。
[編集] 背理法を組み合わせたもの2
-
- P(k) が成立するkが存在すると仮定する。
- P(k) が成立する最小のkに対し、P(k-1) が成立する。
- よってP(k) が成立するkは存在しない。
[編集] 0 以外から始める
ある整数 a から議論を始める。すなわち、次の 2 つを確かめることにより a 以上の任意の整数 k について P(k) が成立することを示す。
- P(a)は真である。
- a 以上の任意の整数 k に対し、P(k) が真であれば、P(k+1) も真である。
[編集] 先立つすべての結果を用いる
仮定として P(k) だけでなく P(0) から P(k) までのすべてを用いる。
- P(0) は真である。
- 任意の自然数 k に対し、P(0), P(1), P(2), ..., P(k) が真であれば、P(k+1) も真である。
[編集] 超限帰納法
自然数について定義された数学的帰納法は、任意の整列集合に対して一般化される。この一般化のことを超限帰納法という。
- S を整列集合とし、P(x) を S の元 x によって定まる命題とする。もし次の 2 つが成立するならば、任意の x ∈ S について P(x) は真。
- S の最小元を m とすれば、P(m) は真。
- 任意の a ∈ S をとる。x < a なる任意の S の元について P(x) が真ならば、P(a) も真。
ただし、a = m の場合には a より小さい x は存在しないので、このとき 2 の 「任意の x < a について P(x) が真ならば」 という条件は恒に真であると考えられる。従って、2 は 1 を含んでおり、敢えて 1 を述べなくてもよい。
S = N の超限帰納法を考えると、最小元は 0 なのでこれは上に述べた数学的帰納法の 「先立つすべての結果を用いる」のバリエーションに等しい。
