数学的帰納法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/12/23 19:35 UTC 版)
数学的帰納法（すうがくてききのうほう、英: mathematical induction）は、数学における証明の手法の一つである。
例えば自然数に関する命題 P(n) が全ての自然数 n に対して成り立つことを証明するために、次のような手続きを行う[注 1]。
- P(1) が成り立つことを示す。
- 任意の自然数 k に対して、「P(k) ⇒ P(k + 1)」が成り立つことを示す。
- 1と2の議論から任意の自然数 n について P(n) が成り立つことを結論づける。
概要
自然数に関するペアノの公理の中に、ほぼ等価なものが含まれている。
なお、数学的「帰納」法という名前がつけられているが、数学的帰納法を用いた証明は帰納ではなく、純粋に自然数の構造に依存した演繹論理の一種である。2 により次々と命題の正しさが"伝播"されていき、任意の自然数に対して命題が証明されていく様子が帰納のように見えるためこのような名前がつけられた[1]。ジョン・ウォリスによって、彼の著作Arithmetica Infinitorumの中で、この方法にinductionという名前が与えられたとされる[2][3]。
直観的説明
高校の教科書等の初等的な解説書ではドミノ倒しに例えて数学的帰納法を説明しているものも多い。P(n) を「n 枚目のドミノが倒れる」の意味だとすれば、上の論法は以下のようになる：
- 1枚目のドミノが倒れることを示す。
- 任意の自然数 k に対して、「k 枚目のドミノが倒れるならば k + 1 枚目のドミノが倒れる」ことを示す。
- 以上の議論から全てのドミノが倒れることが結論づけられる。
数学的帰納法が成り立つ直観的理由は以下の通りである。まず1より
- (a) P(1)
が正しいことが分かる。次に k = 1, 2, ... に対して 2 を適用することで、
- (b) P(1) ⇒ P(2),
- (c) P(2) ⇒ P(3),
- …
が分かる。(a), (b) より、P(2) が成り立ち、この事実と (c) を組み合わせることにより P(3) が従う。以下同様に P(4), P(5), … も従い、結局3の
- 全ての自然数 n に対し P(n) が成り立つ
が結論づけられる。
ただし、以上の議論はあくまで数学的帰納法が成り立つ理由の直観的説明であって、1, 2 と 3 の間にはギャップがある。詳しくは後述の「数学的帰納法の形式的な取り扱い」の項目を参照されたい。
証明
数学的帰納法が成り立つことを数学的帰納法の原理といい、ペアノの公理Ⅴ[注 2]が数学的帰納法の原理そのものを表している。もし、公理Vを用いて、数学的帰納法をあえて証明するならば、以下のように示すことができる。
自然数の集合を 
