数学的帰納法とは：定義・原理・証明手順と例によるわかりやすい解説

数学的帰納法は、無限に続く主張（通常はすべての自然数について成り立つ命題）を論理的に証明するための標準的な手法です。直感的には「最初のケースが真で、それが成り立つなら次のケースも成り立つ」と示せれば、すべてのケースについて真であると結論づけられる、という考え方です。

数学的帰納法の原理

基底（ベース）ステップ：最小の値（通常は n = 1）が成り立つことを示す。
帰納ステップ：任意の自然数 n に対して、「n が成り立つと仮定すると、n+1 も成り立つ」ことを示す。

これら二つのステップが成立すれば、基底が成り立つので基底の次（1→2）が成り立ち、さらにその次（2→3）が成り立ち、… と順に全ての自然数について主張が成り立つことになります。数学的にはこれは自然数の順序性（最小元を持つ性質）に基づく論法です。

注意点・バリエーション

強い帰納法（完全帰納法）：帰納仮定として「1,2,…,n のすべてが成り立つ」と仮定し、それを使って n+1 を示す方法。通常の帰納法と等価ですが、証明を簡潔にする場合があります。
基底を複数必要とする場合：主張によっては最小の数だけでなく、最初の数個（例えば n=1,2）を示す必要があることがあります。
誤りに注意：帰納ステップで仮定を用いる際に、既に示した事実や仮定の対象外の値に依存していないか確認してください。

例：1 + 2 + … + n = n(n+1)/2 の証明

命題：すべての自然数 n について

1 + 2 + 3 + … + n = n(n+1)/2

証明（数学的帰納法）：

基底（n = 1）：

左辺は 1、右辺は 1(1+1)/2 = 1 なので等しい。すなわち n = 1 のとき成り立つ。

$2\sum _{k=1}^{1}k=2(1)=1(1+1)$

帰納仮定：ある自然数 n0 に対して命題が成り立つと仮定する：

∑_{k=1}^{n0} k = n0(n0+1)/2

$2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)$

帰納ステップ（n0 → n0+1）：

左辺を n0+1 までの和に拡張すると、

∑_{k=1}^{n0+1} k = (∑_{k=1}^{n0} k) + (n0 + 1).

帰納仮定を代入すると、

∑_{k=1}^{n0+1} k = n0(n0+1)/2 + (n0 + 1).

右辺を共通因子 (n0+1)/2 で整理すると、

n0(n0+1)/2 + (n0 + 1) = (n0+1)(n0/2 + 1) = (n0+1)(n0+2)/2.

したがって、

∑_{k=1}^{n0+1} k = (n0+1)(n0+2)/2。

$2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)$

以上により、基底と帰納ステップの両方が成立するため、命題はすべての自然数 n について成り立つ。

補足：帰納法の妥当性（直観的説明）

数学的帰納法は、「もし 1 が成り立ち、かつ任意の k で k が成り立つなら k+1 も成り立つなら、すべての自然数で成り立つ」という論理的原理に依拠しています。もし反例が存在すると仮定すると、反例の集合は自然数の部分集合であり、自然数の順序性（任意の非空部分集合は最小元を持つ）から最小の反例が存在します。しかしその最小の反例 m > 1 に対して m-1 が成り立つため帰納ステップにより m も成り立ち矛盾する、という形で妥当性が説明できます。

まとめ

数学的帰納法は「基底」と「帰納ステップ」の二段階で無限命題を証明する有力な手段。
強い帰納法や複数基底を用いる変法があり、場合によって使い分ける。
証明を書くときは帰納仮定を明確にし、仮定から n+1 を導く論理の穴がないか注意する。

（上の説明中に用いた数式は直感的な表現も併記しています。）

$n+1$

$1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)$

$2\sum _{k=1}^{n}k=n(n+1)$

$2\sum _{k=1}^{{n_{0}}+1}k$

$2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)$

$2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),$

似たような証明

数学的帰納法は、しばしば開始値0（むしろ1ではなく）で記述されます。実際には、様々な開始値を使っても同じようにうまくいく。開始値が3の場合の例を示す。 n {\displaystyle n} -sided polygonの内角の和は、 (n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ 度である。

初期値は３で、三角形の内角は ( 3 - 2 ) 180 {\displaystyle (3-2)180} $(3-2)180$ 度である。n {\displaystyle n} -sided polygonの内角が (n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ 度だとする。図をn + 1 {\displaystyle n+1}にする三角形をつける。 $n+1$ -辺の多角形、そしてその角度の数を 180 度増やす ( n - 2 ) 180 + 180 = ( n + 1 - 2 ) 180 {\displaystyle (n-2)180+180=(n+1-2)180} $(n-2)180+180=(n+1-2)180$ 度。証明された。

数学的帰納法による証明が機能する数学的対象は非常に多い。専門用語では，整列集合と呼ばれています．

帰納的定義

同じ考えでも、証明するだけでなく、定義するためにも働くことがあります。

Define n {displaystyle n} th degree cousin.

A 1 {displaystyle 1 $1$ } st degree cousin is the child of the parent's sibling.
A n + 1 { } $n+1$ st degree cousin is child of a parent's n { } th degree cousin. A n + 1 { } st degree cousin is a child of a parent's n { } th degree cousin.