数学的帰納法

同義語：mathematical induction帰納法

概要

前提知識: 自然数, 集合, 論理と命題

奇数を小さい順に足していくと
$$ 1=1^2,\quad 1+3=4=2^2,\quad 1+3+5=9=3^2,\quad 1+3+5+7=16=4^2,\quad 1+3+5+7+9=25=5^2 $$
となり、最初の $n$ 個の奇数の和はいつも $n^2$ に見える。しかし何行確かめても、確かめたのは有限個の $n$ だけである。そこで次の 2 つを示す。(1) $n=1$ のとき正しい。(2) ある $n$ で「最初の $n$ 個の奇数の和が $n^2$」が正しいなら、次の奇数 $2n+1$ を足すと $n^2+2n+1=(n+1)^2$ なので、$n+1$ でも正しい。(1) で $n=1$ が正しく、(2) を $n=1$ に使って $n=2$、$n=2$ に使って $n=3$、……と、並べたドミノが次々に倒れるように、すべての $n$ で正しいことが分かる。この論法が 数学的帰納法 である。
数学的帰納法は、自然数全体にわたる無限個の主張を、「最初の場合」と「1 つ進む段階」の 2 つの有限の議論に帰着させる証明法である。和の公式、不等式、整除性、漸化式で定まる数列の一般項、有限集合の元の個数に関する事実など、「すべての $n$ について」という主張の多くがこの方法で証明される。

定義

Mathpedia の流儀に従い、$0$ を自然数に含めて $\mathbb{N}=\{0,1,2,\dots\}$ とする。自然数 $n$ ごとに真偽の定まる主張（命題、論理と命題を参照）$P(n)$ を考える。自然数は $0$ から始めて「$1$ を足す」操作（後者をとる操作）を繰り返して得られるものであり、そこに余分な元はない。これを自然数の記事は Peano 構造の条件 3「$0$ を含み、後者をとる操作で閉じた部分集合は全体に一致する」として定義に組み込んでいる。数学的帰納法はこの条件を主張の言葉で述べ直したものである。

数学的帰納法の原理

自然数 $n$ についての主張 $P(n)$ が次の 2 条件を満たすとする。

（基底段階）$P(0)$ が成り立つ。
（帰納段階）任意の自然数 $n$ について、$P(n)$ が成り立つならば $P(n+1)$ が成り立つ。
このとき、すべての自然数 $n$ について $P(n)$ が成り立つ。

Peano構造の条件3による

$A:=\{n\in\mathbb{N}\mid P(n)\text{ が成り立つ}\}$ とおく（$\mathbb{N}$ の部分集合である）。条件 1 により $0\in A$ である。$n\in A$ なら $P(n)$ が成り立つので、条件 2 により $P(n+1)$ が成り立ち、$n+1\in A$ である。すなわち $A$ は $0$ を含み、後者をとる写像 $n\mapsto n+1$ で閉じている。自然数の記事の定義「Peano構造」の条件 3 により $A=\mathbb{N}$ であり、すべての $n$ について $P(n)$ が成り立つ。$\square$

条件 2 の「$P(n)$ が成り立つならば」の部分の仮定 $P(n)$ を 帰納法の仮定（induction hypothesis）という。帰納段階で示すのは「$P(n)$ そのもの」ではなく「$P(n)$ から $P(n+1)$ が従うこと」であり、$P(n)$ が実際に正しいかどうかはこの段階では問わない。自然数を集合論の中で $0=\emptyset$、$n+1=n\cup\{n\}$ として構成する流儀では、同じ原理は帰納的集合の記事の系「数学的帰納法の原理」として、無限公理が与える最小の帰納的集合から導かれる。
実際の証明では、始点が $0$ でないことが多い。冒頭の奇数の和は $n=1$ から始まる。

始点をずらした帰納法

$m$ を整数とし、$m$ 以上の整数 $n$ についての主張 $P(n)$ を考える。$P(m)$ が成り立ち、$m$ 以上の任意の整数 $n$ について「$P(n)$ ならば $P(n+1)$」が成り立つなら、$m$ 以上のすべての整数 $n$ について $P(n)$ が成り立つ。

番号を付け替える

自然数 $k$ について $Q(k)$ を「$P(m+k)$ が成り立つ」と定める。$Q(0)$ は $P(m)$ なので成り立つ。$Q(k)$ が成り立つとすると、$m+k\ge m$ なので仮定により $P(m+k+1)$、すなわち $Q(k+1)$ が成り立つ。thm-mathind-principle によりすべての $k\in\mathbb{N}$ で $Q(k)$ が成り立つ。$m$ 以上の整数 $n$ は $n=m+k$（$k=n-m\in\mathbb{N}$）と書けるので、$P(n)$ が成り立つ。$\square$

この系は整数全体についての主張には使えない。$P(m)$ と「$P(n)$ ならば $P(n+1)$」から分かるのは $n\ge m$ の場合だけであり、$m$ より小さい $n$ については何も言えない。整数全体で示すには、さらに「$P(n)$ ならば $P(n-1)$」も示す必要がある（Ham §10.1、p. 183）。

直感

数学的帰納法はしばしばドミノ倒しにたとえられる。一列に並んだドミノの最初の 1 枚が倒れ（基底段階）、どのドミノも倒れれば次のドミノを倒す（帰納段階）なら、すべてのドミノが倒れる。どちらか一方だけでは足りない。最初の 1 枚を倒さなければ、隣どうしがいくら近くても 1 枚も倒れない（ex-mathind-no-base）。途中に 1 か所でも隙間があれば、そこから先は倒れない（ex-mathind-horses）。
「帰納法」という名前は、個々の観察から一般法則を推測する「帰納的推論」と紛らわしいが、両者はまったく別物である。帰納的推論は有限個の事例から一般の主張を推測するだけで、正しさは保証されない。数学的帰納法は、基底段階と帰納段階を示せば主張がすべての自然数で正しいことを確定させる、演繹的な証明法である（Ham §10.1、p. 183 でも注意されている）。冒頭の表のように小さい場合を並べることは、主張を推測し帰納段階の計算の見当をつけるのに役立つが、それ自体は証明ではない。

例と反例

奇数の和

正の整数 $n$ について $1+3+5+\cdots+(2n-1)=n^2$ であることを、cor-mathind-shifted を $m=1$ として使って示す。$P(n)$ を「$\sum_{k=1}^{n}(2k-1)=n^2$」とする。
基底段階：$n=1$ のとき左辺は $1$、右辺は $1^2=1$ で等しい。
帰納段階：$n\ge1$ とし、$P(n)$ が成り立つとする。このとき
$$ \sum_{k=1}^{n+1}(2k-1)=\sum_{k=1}^{n}(2k-1)+\bigl(2(n+1)-1\bigr)=n^2+2n+1=(n+1)^2 $$
なので $P(n+1)$ が成り立つ。よってすべての正の整数 $n$ で $P(n)$ が成り立つ。これは Ham の第 10 章の最初の例である（§10.1、p. 182）。$n=0$ を含めて、空の和を $0$ と約束すれば $P(0)$ も成り立ち、$0$ から始めても同じ証明が通る。

2 の冪と自然数

すべての自然数 $n$ について $2^n>n$ である。
基底段階：$2^0=1>0$ である。
帰納段階：$2^n>n$ とする。両辺は整数なので $2^n\ge n+1$ であり、
$$ 2^{n+1}=2\cdot2^n\ge2(n+1)=2n+2>n+1 $$
となる。よって $2^{n+1}>n+1$ である。
この帰納段階では、帰納法の仮定の「$>$」を整数の性質で「$\ge n+1$」に強めてから使っている。仮定 $2^n>n$ をそのまま 2 倍しても $2^{n+1}>2n$ しか得られず、$n=0$ のとき $2n=0<1=n+1$ なので $2^{n+1}>n+1$ に届かない。帰納段階ではしばしば、仮定をどの形で使うかが要点になる。

反例：すべての馬は同じ色である

次の「証明」は誤りである。主張 $P(n)$：「$n$ 頭の馬をどう選んでも、それらはすべて同じ色である」（$n\ge1$）。
基底段階：$1$ 頭の馬は、それ自身と同じ色である。
帰納段階（誤り）：$P(n)$ を仮定し、$n+1$ 頭の馬 $h_1,\dots,h_{n+1}$ をとる。$h_1,\dots,h_n$ は $n$ 頭なので同じ色であり、$h_2,\dots,h_{n+1}$ も $n$ 頭なので同じ色である。両方の組に共通に属する馬がいるので、全体が同じ色である。
誤りは帰納段階にある。「両方の組に共通に属する馬がいる」には、$h_2,\dots,h_n$ が空でないこと、すなわち $n\ge2$ が必要である。$n=1$ のとき 2 つの組は $\{h_1\}$ と $\{h_2\}$ で、共通の馬はいない。したがってこの議論は $n\ge2$ のときの「$P(n)$ ならば $P(n+1)$」は示しているが、$n=1$ のときの「$P(1)$ ならば $P(2)$」は示していない。実際、$P(1)$ は真で $P(2)$ は偽（色の違う 2 頭がいれば反例になる）なので、この含意は偽である。この例は「帰納段階が $n\ge2$ でだけ示されていても、$P(1)$ からすべての $n$ で $P(n)$ が従う」という含意を破っている。cor-mathind-shifted の帰納段階は、始点 $m$ 以上のすべての $n$ について示さなければならない。

反例：基底段階のない「証明」

主張「すべての自然数 $n$ について $n^2+n$ は奇数である」を考える。帰納段階は成り立つ。$n^2+n$ が奇数なら
$$ (n+1)^2+(n+1)=(n^2+n)+2(n+1) $$
は奇数と偶数の和なので奇数である。しかし主張は偽である。$0^2+0=0$ は偶数であり、そもそも $n^2+n=n(n+1)$ は連続する 2 整数の積なのでつねに偶数である。
もっと極端な例として、主張 $n=n+1$ も、両辺に $1$ を足せば $n+1=n+2$ となるので帰納段階は成り立つが、どの $n$ についても偽である。これらの例は「帰納段階だけからすべての $n$ で主張が従う」という含意を破っており、欠けている仮定は基底段階である。帰納段階は「正しい主張が次へ受け渡される」ことしか言っておらず、受け渡すべき最初の正しさは基底段階が与える。

性質

以下では、自然数の大小 $<$ について「$k< n+1$ と $k\le n$ は同値」「$0$ でない自然数 $n$ は $n=m+1$ の形にただ 1 通りに書ける」という基本的な事実を用いる（後者は自然数の記事の命題「基点と後者像による分割」）。

強い帰納法

帰納段階で $P(n)$ だけでなく、それより前のすべての $P(k)$ を仮定してよい形がある。

強い帰納法

自然数 $n$ についての主張 $P(n)$ が次の条件を満たすとする。
任意の自然数 $n$ について、「$k< n$ を満たすすべての自然数 $k$ で $P(k)$ が成り立つ」ならば $P(n)$ が成り立つ。
このとき、すべての自然数 $n$ について $P(n)$ が成り立つ。

前の全部をまとめた主張に帰納法を使う

$Q(n)$ を「$k< n$ を満たすすべての自然数 $k$ で $P(k)$ が成り立つ」と定め、$Q(n)$ に thm-mathind-principle を使う。$0$ より小さい自然数はないので $Q(0)$ は（空虚な真として）成り立つ。$Q(n)$ が成り立つとすると、仮定の条件により $P(n)$ が成り立つ。$k< n+1$ なら $k< n$ または $k=n$ であり、前者では $Q(n)$ により、後者では今示したことにより $P(k)$ が成り立つので、$Q(n+1)$ が成り立つ。よってすべての $n$ で $Q(n)$ が成り立ち、特に $Q(n+1)$ から $P(n)$ が従う。$\square$

強い帰納法には基底段階が別に書かれていないが、なくなったわけではない。条件を $n=0$ に使うと、前提「$k<0$ のすべての $k$ で $P(k)$」は空虚に真なので、結論 $P(0)$ を何も仮定せずに示さなければならない。実際の証明では、帰納段階の議論が小さい $n$ で使えない（前の $2$ 項を使うのに $n\ge2$ が要る、など）ことが多く、その場合は小さい $n$ を個別に確かめる。これが強い帰納法の基底段階にあたる。
強い帰納法の典型的な使い方は、$n$ を $n$ より小さい数に分解する議論である。たとえば $2$ 以上の整数が素数の積に書けることは、$n$ が素数でなければ $n=ab$（$1< a,b< n$）と分解し、$a$ と $b$ に帰納法の仮定を使って示される（素数の記事の定理「算術の基本定理」の証明）。$a$ や $b$ は $n-1$ とは限らないので、通常の帰納法の仮定 $P(n-1)$ だけでは足りない。

2 つ前の項を使う漸化式

数列 $f(1),f(2),\dots$ を $f(1)=3$、$f(2)=5$、$n\ge3$ で $f(n)=2f(n-1)-f(n-2)$ と定める。$f(3)=2\cdot5-3=7$、$f(4)=2\cdot7-5=9$ となり、$f(n)=2n+1$ と予想される（KT17 §3.9、pp. 53–54 の例）。これを強い帰納法（始点を $1$ にずらしたもの）で示す。$P(n)$ を「$f(n)=2n+1$」とし、$n\ge1$ について、$1\le k< n$ のすべての $k$ で $P(k)$ が成り立つと仮定する。

$n=1$、$n=2$ のときは定義から $f(1)=3=2\cdot1+1$、$f(2)=5=2\cdot2+1$ である。
$n\ge3$ のときは $n-1$ と $n-2$ がともに $1$ 以上 $n$ 未満なので、仮定により
$$ f(n)=2f(n-1)-f(n-2)=2(2n-1)-(2n-3)=2n+1 $$
である。
よってすべての $n\ge1$ で $f(n)=2n+1$ である。$n\ge3$ の議論は $P(n-1)$ だけでなく $P(n-2)$ も使うので、通常の帰納法の形「$P(n-1)$ ならば $P(n)$」のままでは進まない。通常の帰納法で示したければ、主張を「$P(n)$ かつ $P(n+1)$」に強めればよい。強い帰納法は、このように主張を強める操作を一般的に行ったものである（prf-mathind-strong の $Q(n)$）。

整列原理

自然数の整列原理

$\mathbb{N}$ の空でない任意の部分集合 $S$ は最小元をもつ。すなわち、ある $m\in S$ があって、すべての $s\in S$ について $m\le s$ である。

最小元がなければ空であることを強い帰納法で示す

$S\subset\mathbb{N}$ が最小元をもたないとして、$S=\emptyset$ を示す。$P(n)$ を「$n\notin S$」とし、thm-mathind-strong の条件を確かめる。$k< n$ のすべての $k$ で $k\notin S$ とする。もし $n\in S$ なら、$S$ の任意の元 $s$ は $s< n$ ではありえない（$s< n$ なら $s\notin S$ のはず）ので $n\le s$ となり、$n$ は $S$ の最小元になって仮定に反する。よって $n\notin S$ である。強い帰納法によりすべての $n$ で $n\notin S$、すなわち $S=\emptyset$ である。対偶をとると、空でない $S$ は最小元をもつ。$\square$

逆に、整列原理から帰納法の原理を導くこともできる。

整列原理による帰納法の原理の証明

$\mathbb{N}$ の空でない部分集合が最小元をもつと仮定すると、thm-mathind-principle の結論が導かれる。

最小の反例をとる

$P(0)$ と「$P(n)$ ならば $P(n+1)$」を仮定し、$S:=\{n\in\mathbb{N}\mid P(n)\text{ が成り立たない}\}$ が空でないとして矛盾を導く。仮定により $S$ は最小元 $m$ をもつ。$P(0)$ が成り立つので $m\neq0$ であり、$m=m'+1$ と書ける。$m'< m$ なので $m$ の最小性から $m'\notin S$、すなわち $P(m')$ が成り立つ。帰納段階により $P(m'+1)=P(m)$ が成り立ち、$m\in S$ に反する。よって $S=\emptyset$ である。$\square$

3 つの原理の関係と最小反例による証明

thm-mathind-principle から thm-mathind-strong が、それから thm-mathind-well-ordering が導かれ、prop-mathind-from-well-ordering で逆向きが導かれた。したがって、自然数の加法と大小についての基本的な事実を前提にすると、帰納法の原理・強い帰納法・整列原理は互いに他を導く。KT17 は整列性を正の整数の基本性質として述べ（Principle 3.1、p. 40）、帰納法の原理（Principle 3.11、p. 49）がそれと論理的に同値であることを注意している。Ham は整列原理を §1.9（p. 30）で述べている。ここで前提にする事実のうち「$0$ でない自然数は後者である」は、自然数の記事では Peano 構造の条件 3 から証明されている（記事の命題「基点と後者像による分割」）。同値は、この事実と大小の基本性質を認めた体系の上での主張である。
prf-mathind-from-well-ordering の形は、そのまま証明の書き方として使われる。「主張が成り立たない $n$ があるとし、その最小のものを $m$ とすると、$m-1$ では成り立つ。これを使って $m$ でも成り立つことを示し、矛盾を導く」。これを 最小反例による証明（proof by smallest counterexample）という（Ham §10.3、p. 191）。無限降下法（正の整数の無限の減少列は存在しないことを使う論法）も同じ原理に基づく。

帰納的な定義と一般化

帰納的な定義

$0!=1$、$(n+1)!=(n+1)\cdot n!$ のように、$n=0$ の値と「$n$ の値から $n+1$ の値を決める規則」を与えて自然数上の写像を定めることを、帰納的な定義（再帰的定義）という。このような写像がただ 1 つ存在することは再帰定理と呼ばれる（再帰定理が範疇性の証明に使われることは自然数の記事の注意「証明の所在と論理的強さ」を参照。KT17 §3.3（p. 41）は和と階乗の再帰的定義が整列性によって全体で定まることを説明している）。和 $\sum_{k=1}^{n}a_k$ や積 $\prod_{k=1}^{n}a_k$、冪 $a^n$ も帰納的に定義され、それらについての公式（ex-mathind-odd-sum など）は帰納法で証明するのが自然である（KT17 §3.3、§3.7）。

超限帰納法と構造的帰納法

thm-mathind-well-ordering を認めれば、thm-mathind-strong は最小反例をとるだけで証明できる。$P(n)$ が成り立たない最小の $n=m$ をとると、$k< m$ のすべてで $P(k)$ が成り立つので、条件から $P(m)$ が成り立ち矛盾する。この議論で使うのは、$\mathbb{N}$ の順序が「空でない部分集合は最小元をもつ」ことだけである。この性質をもつ全順序を整列順序といい、任意の整列集合の上で同じ形の帰納法が成り立つ（整列順序の記事の定理「整列集合上の帰納法の原理」）。順序数全体の上でのこの帰納法を超限帰納法という。また、論理式や木のように「基本的なものから構成規則を有限回使って作られるもの」については、構成の段数に関する帰納法と同じ形の構造的帰納法が使われる。