MathLabs
公理証明済み

数学的帰納法の原理

内容

命題 P(n)P(n) を、自然数 n≥n0n \ge n_0 に依存するものとして考える。（基底段階）P(n0)P(n_0) が真であり、（帰納段階）任意の k≥n0k \ge n_0 に対し P(k)P(k) が真ならば P(k+1)P(k+1) も真であるとき、P(n)P(n) はすべての整数 n≥n0n \ge n_0 について真である。

なぜ正しいのか?

帰納法は無限のはしごを登るようなものである：最初の段に到達でき、どの段からも常に次の段へ到達できるなら、どんなに高くてもすべての段に到達できる。無限に多くの段を一つずつ確認する必要は決してない——最初の一歩と『次の段へ進む』仕組みを確認するだけで、すべてを一度にカバーできる。

証明の概略

この原理は自然数の整列性から従う：{n0,n0+1,… }\{n_0, n_0+1, \dots\} の任意の空でない部分集合は最小元を持つ。集合 SS は、n≥n0n \ge n_0 で P(n)P(n) が偽であるものの集合とする。これが空でないと仮定する（背理法）。その最小元を mm とする。P(n0)P(n_0) は真であるから m≠n0m \ne n_0 であり、したがって m−1≥n0m - 1 \ge n_0 かつ m−1∉Sm-1 \notin S（mm が最小のため）、すなわち P(m−1)P(m-1) は真である。帰納段階により P(m)P(m) も真でなければならず、m∈Sm \in S に矛盾する。よって SS は空であり、P(n)P(n) はすべての n≥n0n \ge n_0 で成り立つ。（同値に、帰納法と N\mathbb{N} の整列性は互いに置き換え可能であり、どちらもペアノの公理から従う。）

提示者

1654年に提示ブレーズ・パスカル

この定理を使うトピック

数学的帰納法

ステップごとの証明

この定理のステップごとの証明はまだありません。

参考文献

  1. Kenneth H. Rosen (2012). Discrete Mathematics and Its Applications
  2. George Pólya (1954). Induction and Analogy in Mathematics