数学的帰納法

数学的帰納法は、ある命題が正しいことを証明する方法である。 $P(n)$ すべての自然数に対して真である $n$ つまり、無限に多くのケース $P(0),P(1),P(2),P(3),\dots$ すべて成り立つ。これは、まず単純なケースを証明し、次に、あるケースで主張が真であると仮定すれば、次のケースも真であることを示すことによって行われる。ドミノ倒しやはしご登りなどの非公式な比喩は、この手法を説明するのに役立つ。

数学的帰納法は、はしごの最下段（基底）に登ることができ、各段から次の段（ステップ）に登ることができることを証明することで、はしごを好きなだけ高く登ることができることを証明します。

—具体的な数学、3ページ余白。

帰納法による証明は2つの場合から構成される。最初の基本ケースは、次の命題を証明する。 $n=0$ 他のケースに関する知識を一切仮定せずに。2番目のケースである帰納ステップでは、任意のケースで命題が成り立つ場合、 $n=k$ ならば、次のケースにも当てはまるはずだ $n=k+1$ これらの2つのステップにより、この命題がすべての自然数に対して成り立つことが証明される。 $n$ 基本ケースは必ずしも以下から始まるとは限りません $n=0$ しかし多くの場合、 $n=1$ 、また、任意の固定された自然数と組み合わせることも可能 $n=N$ すべての自然数に対してこの命題が真実であることを証明する $n\geq N$ 。

この方法は、木などのより一般的な正則構造に関する命題を証明するために拡張できます。構造帰納法として知られるこの一般化は、数理論理学やコンピュータ科学で使用されています。この拡張された意味での数学的帰納法は、再帰と密接に関連しています。数学的帰納法は、形式的証明で使用される推論規則であり、コンピュータプログラムのほとんどの正当性証明の基礎となっています。^[³^]

その名称とは裏腹に、数学的帰納法は、哲学で用いられる帰納的推論とは根本的に異なる。哲学では、多くの事例を検討することで蓋然性の高い結論が得られる。数学的方法は、無限に多くの事例を検討して一般的な命題を証明するが、それは変数を含む有限の演繹的推論の連鎖によって行われる。 $n$ これは無限に多くの値をとることができる。結果として得られるのは、その命題の厳密な証明であり、その確率の主張ではない。^{[ 4 ]}

歴史

デイビッド・E・ジョイスによれば、ユークリッドの著作には数学的帰納法の原理が用いられた証拠はない。 ^{[ 5 ]}ファビオ・アチェルビは2000年に、プラトンの『パルメニデス』（紀元前370年頃）には初期の暗黙の帰納的証明の痕跡が含まれていると主張した。^{[ 6 ]}この解釈は2021年にネグレポンティスとファルマキによって異議を唱えられ、彼らはさらにプラトンも他のピタゴラス派も数学的帰納法の原理を用いなかったと述べている。^{[ 7 ]}

数学的帰納法による最古の暗黙的証明は、紀元1000年頃にアル・カラジによって書かれ、彼はそれを等差数列に適用して二項定理とパスカルの三角形の性質を証明した。元の著作は失われているが、後に紀元1150年頃にアル・サマーワル・アル・マグリービーが著書『アル・バヒル・フィ・ル・ジャブル』（代数学の天才）の中で言及している。^{[ 8 ]}^{[ 9 ]}^{[ 10 ]}

カッツは数学史の中でこう述べている。

アル・カラジが導入し、アル・サマーウアルらが引き継いだもう一つの重要なアイデアは、特定の算術数列を扱うための帰納的議論でした。このように、アル・カラジは、アーリヤバタが既に知っていた整数立方数の和に関する結果を証明するために、そのような議論を使用しました。[ ...] しかし、アル・カラジは任意のnに対する一般的な結果を述べませんでした。彼は特定の整数 10 に対して定理を述べました。[...] しかし、彼の証明は明らかに他の任意の整数に拡張できるように設計されていました。[...] アル・カラジの議論は本質的に、現代の帰納的議論の 2 つの基本要素、すなわちn = 1 (1 = 1 ³ )の場合の命題の真偽と、 n = k − 1の場合の真偽の導出を含みます。もちろん、この 2 番目の要素は明示的ではありません。なぜなら、ある意味で、アル・カラジの議論は逆になっているからです。つまり、彼はn = 10 から始めて 1 まで下降していくのであって、上方向に進んでいくのではない。それにもかかわらず、アル・ファクリにおける彼の議論は、整数立方数の和の公式の現存する最古の証明である。^[¹¹^]

インドでは、数学的帰納法による初期の暗黙的証明が、バスカラの「循環的方法」に現れている。^{[ 12 ]}

（ヴァッカが書いたこととは反対に、フロイデンタールが注意深く示したように）^{[ 13 ]}もう一つの類似例は、フランチェスコ・マウロリコが『算術の書二部作』 （1575年）で、この手法を用いて最初の $n個の$ 奇数の和が $n 2$ であることを証明した例である。

帰納法の最も初期の厳密な使用はゲルソニデス（1288–1344）によるものでした。^{[ 14 ]}^{[ 15 ]}帰納法の原理の最初の明示的な定式化は、パスカルが著書『三角形算術論』 （1665）で示しました。もう一人のフランス人、フェルマーは、関連する原理である無限降下による間接証明を大いに利用しました。

帰納法の仮説はスイスのヤコブ・ベルヌーイによっても用いられ、それ以来広く知られるようになった。この原理の現代的な形式的扱いは、ジョージ・ブール^{[ 16 ]} 、オーガスタス・ド・モルガン、チャールズ・サンダース・パース[ ^{17 ] [}^{18 ] 、}ジュゼッペ・ペアノ、リヒャルト・デデキント^[¹²^]によって19世紀になって初めて行われた。

説明

数学的帰納法の最も単純で一般的な形式は、自然数 $n$ (つまり、 $n \geq 0$ または 1 の整数)を含む命題が、 $n$ のすべての値に対して成り立つことを推論するものです。証明は次の 2 つのステップから構成されます。

の基本ケース（または初期ケース）：0または1の場合にこの命題が成り立つことを証明する。
の帰納ステップ（または帰納的ステップ、ステップケース）：任意の $n$ 、命題が $n$ $で成り立つならば、 n + 1$ でも成り立つ。言い換えれば、任意の自然数 $n$ 、命題が $n + 1$ 。

帰納段階における仮説、すなわち特定の $nに対して命題が成り立つという仮説は、$ 帰納仮説または帰納的仮説と呼ばれます。帰納段階を証明するには、まず $n$ に対して帰納仮説を仮定し、次にこの仮定を用いて、命題が $n + 1$ に対しても成り立つことを証明します。

自然数を0から定義することを好む著者は、その値を基本ケースとして使用し、自然数を1から定義することを好む著者は、その値を基本ケースとして使用します。

例

連続する自然数の和

数学的帰納法を用いることで、すべての自然数について以下の命題を証明することができる。 $n\geq 0$ : $P(n)\!:\ \ 0+1+2+\cdots +n={\frac {n(n+1)}{2}}.$

これは、与えられた数以下の自然数の和を表す一般的な公式を示しています。実際には、無限に続く一連の記述です。 $0={\tfrac {(0)(0+1)}{2}}$ 、 $0+1={\tfrac {(1)(1+1)}{2}}$ 、 $0+1+2={\tfrac {(2)(2+1)}{2}}$ など

命題。すべての $n\in \mathbb {N}$ 我々はそれを持っている $0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.$

証明。 $P(n)$ 声明である $0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.$ 我々は帰納法による証明を与える $n$ 。

基本ケース：最小の自然数 $n = 0$ に対してこの命題が成り立つことを示せ。

$P(0)$ 明らかに真実です。 $0={\tfrac {0(0+1)}{2}}\,.$

帰納ステップ：すべての $k\geq 0$ 、もし $P(k)$ 保持して、 $P(k+1)$ これも当てはまる。

特定の帰納的仮説を仮定する $k$ 単一のケース $n=k$ 保持する、つまり $P(k)$ 真実です。 $0+1+\cdots +k={\frac {k(k+1)}{2}}.$ したがって、次のことが言える。 $(0+1+2+\cdots +k)+(k+1)={\frac {k(k+1)}{2}}+(k+1).$

代数的に、右辺は次のように簡略化されます。 ${\begin{aligned}{\frac {k(k+1)}{2}}+(k+1)&={\frac {k(k+1)+2(k+1)}{2}}\\&={\frac {(k+1)(k+2)}{2}}\\&={\frac {(k+1)((k+1)+1)}{2}}.\end{aligned}}$

左辺と右辺を等しいとおくと、次のことが導き出されます。 $0+1+2+\cdots +k+(k+1)={\frac {(k+1)((k+1)+1)}{2}}.$ つまり、声明 $P(k+1)$ これも同様に当てはまり、帰納段階を確立する。

結論：基本ケースと帰納ステップの両方が真であることが証明されたので、数学的帰納法により次の命題が成り立つ。 $P(n)$ すべての自然数に対して成り立つ $n\geq 0$ 証明終了

三角関数の不等式

帰納法は不等式を証明するためによく用いられる。例として、次のことを証明する。 $\left|\sin nx\right|\leq n\left|\sin x\right|$ 任意の実数に対して $x$ および自然数 $n$ 。

一見すると、より一般的なバージョンでは、 $\left|\sin nx\right|\leq n\left|\sin x\right|$ 任意の実数に対して $n,x$ 帰納法を用いなくても証明できるが、 ${\textstyle n={\frac {1}{2}},\,x=\pi }$ 非整数値の場合、偽となる可能性があることを示している $n$ これは、自然値に関して特にその記述を検証することを示唆している。 $n$ そして、誘導法が最も手軽な手段である。

命題。任意の $x\in \mathbb {R}$ そして $n\in \mathbb {N}$ 、 $\left|\sin nx\right|\leq n\left|\sin x\right|$ 。

証明。任意の実数を固定する。 $x$ 、そして $P(n)$ 声明である $\left|\sin nx\right|\leq n\left|\sin x\right|$ . 私たちは $n$ 。

基本ケース：計算 $\left|\sin 0x\right|=0\leq 0=0\left|\sin x\right|$ 検証する $P(0)$ 。

帰納ステップ：含意を示す $P(k)\implies P(k+1)$ 任意の自然数に対して $k$ 帰納法の仮説を仮定する：与えられた値に対して $n=k\geq 0$ 単一のケース $P(k)$ これは正しい。角度の加法公式と三角形の不等式を用いると、次のことが導き出される。 ${\begin{aligned}\left|\sin(k+1)x\right|&=\left|\sin kx\cos x+\sin x\cos kx\right|&&{\text{(angle addition)}}\\&\leq \left|\sin kx\cos x\right|+\left|\sin x\,\cos kx\right|&&{\text{(triangle inequality)}}\\&=\left|\sin kx\right|\left|\cos x\right|+\left|\sin x\right|\left|\cos kx\right|\\&\leq \left|\sin kx\right|+\left|\sin x\right|&&(\left|\cos t\right|\leq 1)\\&\leq k\left|\sin x\right|+\left|\sin x\right|&&{\text{(induction hypothesis}})\\&=(k+1)\left|\sin x\right|.\end{aligned}}$

左端と右端の量の不等式は、 $P(k+1)$ これは真であり、帰納的ステップが完了する。

結論：提案 $P(n)$ すべての自然数に当てはまる $n.$ 証明終了

バリエーション

実際には、帰納法による証明は、証明すべき性質の正確な性質に応じて、しばしば異なる構造をとります。帰納法のすべての変種は、超限帰納法の特殊な場合です。以下を参照してください。

0または1以外の基本ケース

$ある命題を、すべての自然数に対してではなく、ある数b$ 以上のすべての数 $n$ に対してのみ証明したい場合、帰納法による証明は次のようになります。

$n = b$ の場合にこの命題が成り立つことを示す。
任意の数 $n \geq b$ に対してこの命題が成り立つならば、同じ命題が $n + 1$ に対しても成り立つことを示す。

これは、例えば、 $n$ $\geq 3$ の場合、 $2 n \geq n + 5 で$ あることを示すために使用できます。

このようにして、ある命題 $P (n) が$ すべての $n \geq 1$ に対して、あるいはすべての $n \geq -5$ に対して成り立つことを証明できる。この形式の数学的帰納法は、実際には前の形式の特殊なケースである。なぜなら、証明すべき命題が $P (n)$ である場合、これら 2 つの規則を使用してそれを証明することは、帰納法の基本ケース $0$ を使用してすべての自然数 $nに対して$ $P (n + b)$ を証明することと同等だからである。^[¹⁹^]

例：硬貨でドル金額を算定する

$4ドル硬貨と5ドル硬貨が無限に供給されていると仮定します。帰納法を用いて、$ $12ドル$ 以上の任意の整数ドルは、これらの硬貨の組み合わせによって構成できることを証明できます。S $(k)を「$ $k$ ドルは4ドル硬貨と5ドル硬貨の組み合わせによって構成できる」という命題とします。S $($ $k$ $)がすべての$ $k$ $\geq 12$ に対して真であることは $、$ $k$ に関する帰納法によって次のように証明できます。

基本ケース: $k$ $= 12の場合に$ $S (k)$ が成り立つことを示すのは簡単です。4 ドル硬貨を 3 枚用意します。

帰納ステップ: $S (k)が$ $k \geq 12$ のある値に対して成り立つ(帰納仮説)と仮定して、 $S (k + 1)$ も成り立つことを証明します。任意の $k$ $\geq 12に対して$ $S (k)$ が真であると仮定します。少なくとも 1 枚の 4 ドル硬貨を含む $k$ ドルの解が存在する場合、それを 5 ドル硬貨に置き換えて $k$ $+$ $1$ ドルにします。そうでない場合、5 ドル硬貨のみを使用する場合は、 $k は5 の倍数でなければならず、少なくとも 15 でなければなりません。しかし、その場合、3 枚の 5 ドル硬貨を 4 枚の 4 ドル硬貨に置き換えて$ $k$ $+$ $1$ ドルにすることができます。いずれの場合も、 $S$ $($ $k$ $+$ $1)$ は真です。

したがって、帰納法の原理により、 $S (k)$ $はすべてのk\geq12$ $に対して$ 成り立ち、証明は完了する。

この例では、 $S (k)$ も成り立つが、 ${\textstyle k\in \{4,5,8,9,10\}}$ 上記の証明は、最小金額である $12$ ドルをより低い値 $mに置き換えるように変更すること$ $はできません$ $。m = 11$ の場合、基本ケースは実際には偽です。m $= 10$ の場合、帰納ステップの 2 番目のケース (3 枚の 5 ドル硬貨を 4 枚の 4 ドル硬貨に置き換える) は機能しません。さらに低い $m$ の場合はなおさらです。

複数のカウンターでの誘導

$2つの自然数n$ と $mを$ 含む命題を、帰納法を繰り返して証明することが望ましい場合がある。つまり、 $n$ について基本ケースと帰納ステップを証明し、それぞれのステップにおいて $m$ について基本ケースと帰納ステップを証明する。例えば、自然数の加算に伴う可換性の証明を参照されたい。3つ以上のカウンタを含む、より複雑な議論も可能である。

無限降下

無限降下法は、ピエール・ド・フェルマーが用いた数学的帰納法の変形である。これは、ある命題 $Q (n) が$ すべての自然数 $n$ に対して偽であることを示すために用いられる。その伝統的な形式は、ある自然数 $nに対して$ $Q (n)$ が真である場合、厳密に小さい自然数 $m$ に対しても真であることを示すことである。自然数の無限減少列は存在しないため、このような状況はあり得ず、それによって (背理法によって) $Q$ $($ $n$ $)はどの$ $n$ に対しても真ではあり得ないことが示される。

$この方法の妥当性は、通常の数学的帰納法の原理から検証できます。「 Q$ $($ $m$ $)は$ $n$ 以下のすべての自然数 $m$ に対して偽である」と定義された命題 $P (n)$ に数学的帰納法を用いると、 $P$ $($ $n$ $)はすべての$ $n$ に対して成り立つことがわかり、これは $Q$ $($ $n$ $)が$ すべての自然数 $n$ に対して偽であることを意味します。

限定的な数学的帰納法

$固定されたN$ 以下のすべての自然数に対して性質 $P$ が成り立つことを証明したい場合は、 $P が$ 次の条件を満たすことを証明すれば十分です。^[²⁰^]

$P$ は0に対して成り立つ。
$N$ より小さい任意の自然数 $x$ に対して、 $x$ について $P$ が成り立つならば、 $x$ $+ 1についても$ $P$ が成り立つ。

接頭辞誘導

数学的帰納法による最も一般的な証明形式は、帰納段階で次のことを証明する必要がある。 $\forall k\,(P(k)\to P(k+1))$

$そこで帰納法の原理は、 P$ $(0)から$ $P$ $($ $n$ $)$ に至る過程で、このステップを $n回$ 「自動化」する。これは「前者帰納法」とも呼ばれる。なぜなら、各ステップでは、ある数の前者に関する情報から、その数に関する情報が証明されるからである。

計算複雑性理論で興味深い変種の一つに「接頭辞帰納法」があり、これは帰納段階で以下の命題を証明するものである。 $\forall k\,(P(k)\to P(2k)\land P(2k+1))$ または同等に $\forall k\,\left(P\!\left(\left\lfloor {\frac {k}{2}}\right\rfloor \right)\to P(k)\right)$

帰納法原理は、 $P$ $(0)から$ $P$ $($ $n$ $)$ に至る過程で、この推論をlog ₂ n回適用することを「自動化」します。実際、これは「接頭辞帰納法」と呼ばれています。なぜなら、各ステップでは、ある数の「接頭辞」（その数の二進数表現の最下位ビットを切り捨てて形成されるもの）に関する情報から、その数に関する何らかの情報を証明するからです。また、これは、その二進数表現の長さに関する従来の帰納法の応用と見なすこともできます。

従来の先行帰納法を計算論的に $nステップのループと解釈するならば、前置帰納法はlog$ $n$ ステップのループに相当する。そのため、前置帰納法を用いた証明は、先行帰納法を用いた証明よりも「より実行可能で構成的」である。

先行誘導は、同じ文に対して前置誘導を自明にシミュレートできます。前置誘導は先行誘導をシミュレートできますが、文の構文をより複雑にする（有界全称量化子を追加する）という代償を伴うため、前置誘導と多項式時間計算に関連する興味深い結果は、無界量化子を完全に除外し、文で許容される有界全称量化子と存在量化子の交替を制限することに依存します。 ^{[ 21 ]}

この考えをさらに一歩進めて証明する必要がある。 $\forall k\,\left(P\!\left(\left\lfloor {\sqrt {k}}\right\rfloor \right)\to P(k)\right)$ そこで、帰納法の原理は、 $P$ $(0)から$ $P$ $($ $n$ $)$ に至る際に、この推論を $log log n$ 回適用することを「自動化」する。この形式の帰納法は、同様に、対数時間並列計算の研究にも用いられてきた。

完全な（強力な）誘導

完全帰納法、値帰納法、または強帰納法と呼ばれる別の変種（これに対し、帰納法の基本形は弱帰納法と呼ばれることもある）では、より強い仮説を用いることで帰納段階の証明が容易になる。すなわち、次の命題を証明する。 $P(m+1)$ という仮定の下で $P(n)$ すべての自然数に当てはまる $n$ 未満 $m+1$ 対照的に、基本形式は $P(m)$ 「強い帰納法」という名称は、この方法が「弱い帰納法」よりも多くのことを証明できるという意味ではなく、単に帰納段階で使用される仮説がより強いことを指しているにすぎない。

実際、以下に説明するように、2 つの方法は実際には等価であることが示されます。この形式の完全な帰納法では、基本ケースを証明する必要があります。 $P(0)$ 、さらに次のような基本ケース以外のケースを証明する必要が生じる場合もある。 $P(1)$ 一般的な議論が適用される前、例えば以下のフィボナッチ数列の例のように $F_{n}$ 。

先ほど説明した形式では基本ケースを証明する必要があるが、証明できればこれは不要である。 $P(m)$ （仮定すると） $P(n)$ すべての下位 $n$ ) すべての $m\geq 0$ これは、後述する超限帰納法の特殊なケースですが、通常の帰納法とは等価ではありません。この形式では、基本ケースはケースに包含されます。 $m=0$ 、どこ $P(0)$ 他の方法で証明されていない $P(n)$ 想定される。このケースは個別に処理する必要があるかもしれないが、同じ議論が適用される場合もある。 $m=0$ そして $m>0$ 証明をより簡潔かつ優雅にする。ただし、この方法では、証明が $P(m)$ 暗黙のうちに前提としていない $m>0$ 例えば「任意の $n<m$ $または、 m$ 個の要素の集合に1つの要素があると仮定することによって。

通常の帰納法との等価性

完全帰納法は、一方の方法による証明を他方の方法による証明に変換できるという意味で、上述の通常の数学的帰納法と同等である。 $P(n)$ 完全帰納法による。次に、より強い帰納的仮説を仮定することで、この証明を通常の帰納的証明に変換することができる。 $Q(n)$ 「 $P(m)$ すべての $m$ そのため $0\leq m\leq n$ —これが通常の帰納法の帰納的仮説となる。次に、 $Q(0)$ そして $Q(n+1)$ のために $n\in \mathbb {N}$ のみを想定 $Q(n)$ そして、 $Q(n)$ 暗示する $P(n)$ [ ²²^]

一方、 $P(n)$ 通常の帰納法によって証明されていた場合、その証明は実質的に完全な帰納法による証明となるだろう。 $P(0)$ 基本ケースでは仮定なしで証明されており、 $P(n+1)$ 帰納段階で証明され、それまでのすべてのケースを仮定できますが、ケースだけを使用すればよいのです。 $P(n)$ 。

例：フィボナッチ数列

完全帰納法は、各帰納ステップで帰納的仮説の複数の例が必要な場合に最も有用です。たとえば、完全帰納法は、次のことを示すために使用できます。 $F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}$ どこ $F_{n}$ は $n$ 番目のフィボナッチ数であり、 ${\textstyle \varphi ={\frac {1}{2}}(1+{\sqrt {5}})}$ （黄金比）と ${\textstyle \psi ={\frac {1}{2}}(1-{\sqrt {5}})}$ は多項式の根です $x^{2}-x-1$ 事実を利用して $F_{n+2}=F_{n+1}+F_{n}$ 各 $n\in \mathbb {N}$ 上記の恒等式は、直接計算によって検証できます。 ${\textstyle F_{n+2}}$ 両方に既に当てはまると仮定する ${\textstyle F_{n+1}}$ そして ${\textstyle F_{n}}$ 証明を完了するには、次の2つの基本ケースで同一性を検証する必要があります。 $n=0$ そして ${\textstyle n=1}$ 。

例：素因数分解

完全帰納法による別の証明では、この命題がすべてのより小さい値に対して成り立つという仮定を用いる。 $n$ より詳しく見ていきましょう。「 1より大きいすべての自然数は（1つ以上の）素数の積である」という命題を考えてみましょう。これは算術の基本定理の「存在」の部分です。帰納法の段階を証明するための帰納法の仮説は、与えられた自然数に対して、次のようになるということです。 $m>1$ この声明は、より小さなすべてのものにも当てはまります $n>1$ 。もし $m$ が素数であれば、それは間違いなく素数の積であり、そうでなければ、定義によりそれは積である。 $m=n_{1}n_{2}$ 、どちらの因子も 1 に等しくないため、どちらも等しくありません。 $m$ 、したがって両方とも1より大きく、より小さい $m$ 帰納仮説は今や以下に適用されます。 $n_{1}$ そして $n_{2}$ なので、それぞれが素数の積になります。したがって $m$ は素数の積の積であり、したがって拡張すると素数自体の積である。

例：金額の再検討

先ほどと同じ例を、今回は強い帰納法を用いて証明してみましょう。主張の内容は変わりません。 $S(n):\,\,n\geq 12\implies \,\exists \,a,b\in \mathbb {N} .\,\,n=4a+5b$

しかし、拡張された基本ケースから始まる証明の構造と前提条件には若干の違いが生じるだろう。

証拠。

基本ケース:示す $S(k)$ 保持する $k=12,13,14,15$ 。 ${\begin{aligned}4\cdot 3+5\cdot 0=12\\4\cdot 2+5\cdot 1=13\\4\cdot 1+5\cdot 2=14\\4\cdot 0+5\cdot 3=15\end{aligned}}$

基本ケースは成立する。

帰納ステップ：いくつかの $j>15$ 、仮定する $S(m)$ すべての $m$ と $12\leq m<j$ 証明せよ $S(j)$ 保持する。

選択する $m=j-4$ 観察すると、 $15<j\implies 12\leq j-4<j$ 示しているのは $S(j-4)$ 帰納的仮説により、次の式が成り立つ。すなわち、合計 $j-4$ は、いくつかの組み合わせによって形成されます。 $4$ そして $5$ ドル硬貨。次に、 $4$ その組み合わせにドル硬貨を加えると合計が $j$ つまり、 $S(j)$ 成立する。^{[ 23 ]}証明終了

順方向・逆方向誘導

時には、逆算して、次の命題を証明する方が都合が良い。 $n-1$ その妥当性を考慮すると、 $n$ しかし、単一の数について命題の妥当性を証明するだけでは基本ケースを確立するには不十分であり、代わりに自然数の無限部分集合について命題を証明する必要がある。例えば、オーギュスタン・ルイ・コーシーは、まず順方向（正則）帰納法を用いて 2のすべてのべき乗について算術平均と幾何平均の不等式を証明し、次に逆方向帰納法を用いてすべての自然数についてそれを示しました。^[²⁴^]^[²⁵^]

帰納段階における誤りの例

帰納法のステップは、 $nのすべての値に対して証明されなければなりません。これを説明するために、ジョエル・E・コーエンは、$ すべての馬が同じ色であることを数学的帰納法によって証明しようとする次の議論を提案しました。^{[ 26 ]}

基本ケース：馬が1頭だけのセットの場合、色は1種類のみです。

帰納ステップ:帰納仮説として、任意の集合内で $n$ 馬には、色は1種類しかありません。 $n+1$ 馬。番号を振ってください。 $1,2,3,\dotsc ,n,n+1$ 集合を考えてみましょう ${\textstyle \left\{1,2,3,\dotsc ,n\right\}}$ そして ${\textstyle \left\{2,3,4,\dotsc ,n+1\right\}}$ それぞれは、 $n$ 馬は複数存在するので、それぞれの馬の中には色は1つしかない。しかし、2つの集合は重なり合っているため、すべての馬の中に色は1つしかないはずである。 $n+1$ 馬。

基本ケース $n=1$ これは自明であり、帰納法のステップはすべての場合において正しい。 $n>1$ しかし、帰納段階で使用された議論は、 $n+1=2$ なぜなら、「2 つの集合が重なり合う」という記述は、 ${\textstyle \left\{1\right\}}$ そして ${\textstyle \left\{2\right\}}$ 。

形式化

二階述語論理では、「帰納法の公理」は次のように記述できる。 $\forall P\,{\Bigl (}P(0)\land \forall k{\bigl (}P(k)\to P(k+1){\bigr )}\to \forall n\,{\bigl (}P(n){\bigr )}{\Bigr )},$ ここで、 $P (\cdot)$ は1 つの自然数を含む述語の変数であり、 $k$ と $n は$ 自然数の変数です。

言い換えれば、基本ケース $P (0)$ と帰納ステップ（すなわち、帰納仮説 $P (k)が$ $P (k + 1)$ を意味すること）を合わせると、任意の自然数 $nに対して$ $P (n)$ が成り立つことが導かれる。帰納法の公理は、基本ケースと帰納ステップから任意の自然数 $nに対して$ $P$ $($ $n$ $)$ が成り立つと推論することの妥当性を主張する。

この公理の最初の量化子は、個々の数値ではなく述語を対象としています。これは二階述語論理の量化子であり、この公理が二階述語論理で記述されていることを意味します。一階述語論理で算術帰納法を公理化するには、考えられる各述語ごとに個別の公理を含む公理図式が必要です。この問題については、「ペアノ公理」の記事でさらに詳しく解説されています。

自然数に関する構造帰納法の公理は、最初にペアノによって定式化され、彼はそれを用いて、以下の4つの公理とともに自然数を規定した。

0は自然数である。
すべての自然数の後継関数 $s$ は自然数を生成します $（ s （ x ）= x +1）$ 。
後継関数は単射である。
0 は $s$ の範囲に含まれません。

一階 ZFC集合論では、述語に対する量化は許されないが、帰納法は集合に対する量化によって表現することができる。 $\forall A{\Bigl (}0\in A\land \forall k\in \mathbb {N} {\bigl (}k\in A\to (k+1)\in A{\bigr )}\to \mathbb {N} \subseteq A{\Bigr )}$ $Aは$ 、命題を表す集合であり、その命題が成り立つ自然数を含む集合と解釈できる。これは公理ではなく定理である。なぜなら、ZFC集合論の言語では、自然数はペアノの公理に類似した公理によって定義されているからである。無限公理と仕様公理図式を用いた自然数の構成を参照のこと。

超限誘導

完全帰納法の原理の変形の一つは、任意の整礎集合の要素に関する命題に一般化することができる。整礎集合とは、反射的でない関係< を持ち、無限に下降する連鎖を持たない集合のことである。順序数を表すすべての集合は整礎集合であり、自然数の集合もその一つである。

整礎集合に適用すると、超限帰納法は単一のステップとして定式化できます。各序数nに対して命題 $P (n)が成り立つことを証明するには、次の手順が必要です。$

各序数 $n$ について、 $m$ $<$ $nのすべての m に対して$ $P (m)$ が成り立つならば、 $P$ $($ $n$ $)$ も成り立つことを示せ。

この形式の帰納法を順序数の集合（整列した、したがって整礎的なクラスを形成する）に適用すると、超限帰納法と呼ばれる。これは集合論、位相幾何学、その他の分野における重要な証明手法である。

超限帰納法による証明では、通常、次の3つの場合が区別されます。

$n$ が最小要素である場合、つまり $n$ より小さい要素が存在しない場合。
$n$ が直接の前任者を持つ場合、つまり $n$ より小さい要素の集合に最大の要素が存在する場合。
$n$ に直接の前任者がいない場合、つまり $n$ はいわゆる極限順序数です。

厳密に言えば、超限帰納法では基本ケースを証明する必要はありません。なぜなら、それは「もし $P が$ すべての $n$ $<$ $m$ に対して真ならば、 $P$ $はm$ に対して真である」という命題の空虚な特殊ケースだからです。この命題が空虚に真であるのは、まさに反例となり得る $n$ $<$ $m$ の値が存在しないからです。したがって、特殊ケースは一般ケースの特殊ケースなのです。

整列原理との関係

数学的帰納法の原理は、通常、自然数の公理として述べられます（ペアノ公理を参照）。他のペアノ公理の文脈では、整列原理よりも厳密に強い原理です。次のことを仮定します。

三分割公理：任意の自然数 $n$ と $m$ について、 $nが$ $m$ 以下であることと、 $m が$ $n$ より小さくないことは同値である。
任意の自然数 $n$ に対して、 $n + 1$ はnより大きい。
任意の自然数 $n$ に対して、nと $n$ $+$ $1$ の間に自然数は存在しない。
自然数で0より小さい数は存在しない。

以上の公理を前提とすれば、帰納法は整列原理を導くことが証明できる。以下の証明では、完全帰納法と第一および第四の公理を用いる。

証明。自然数の空でない集合 $S$ が存在し、最小元を持たないと仮定する。n が S に含まれないという主張を P(n) とする $。P$ $($ 0 ) は $真である。$ なぜなら、 $P$ $(0)が偽であれば、0 は$ $S$ の最小元となるからである。さらに、 $n を$ 自然数とし、 $n$ $+$ $1$ より小さいすべての自然数 $mに対して$ $P$ $($ $m$ $)$ が真であると仮定する $。P$ $($ $n$ $+$ $1)$ が偽であれば、 $n$ $+$ $1は$ $S$ に含まれることになり、 $S$ の最小元となるため矛盾が生じる。したがって、 $P$ $($ $n$ $+$ $1)$ は真である。したがって、完全帰納法の原理により、 $P$ $($ $n$ $) は$ すべての自然数 $n$ に対して成り立つ。したがって、 $S$ は空集合となり矛盾が生じる。証明終了

集合

{(0,

n

):

n

\in

N

}

\cup

{(1,

n

):

n

\in

N

}

の「数直線」。数値はペアの2番目の要素を指し、最初の要素は色または位置から取得できます。

一方、セットは $\{(0,n):n\in \mathbb {N} \}\cup \{(1,n):n\in \mathbb {N} \}$ 図に示すように、は辞書式順序によって整列している^{[ 27 ]}^{： 35lf}。さらに、帰納法の公理を除いて、すべてのペアノ公理を満たしている。ここで、ペアノ定数0はペア(0, 0)として解釈され、ペアノの後継関数は、すべてのに対して $succ($ $x$ $,$ $n$ $) = ($ $x$ $,$ $n$ $+$ $1)$ によってペア上で定義される。 $x\in \{0,1\}$ そして $n\in \mathbb {N}$ 帰納法の公理違反の例として、述語 $P (x, n)$ を $(x, n) = (0,0)$ または $(x, n) = succ(y, m)$ と定義する。 $y\in \{0,1\}$ そして $m\in \mathbb {N}$ すると、基本ケース $P (0, 0)$ は自明に真であり、帰納ステップも真です。P $($ $x$ $,$ $n$ $)$ ならば $P$ $(succ($ $x$ $,$ $n$ $))$ です。ただし、 $P$ $(1,0)は偽であるため、$ $P$ $は$ セット内のすべてのペアに対して真ではありません。

帰納法原理を用いたペアノの公理は、自然数を独自にモデル化する。帰納法原理を整列原理に置き換えることで、すべての公理を満たすより複雑なモデルが可能になる。^{[ 27 ]}

いくつかの書籍^{[ 27 ]}や資料では、整列原理が帰納法の公理と等価であると誤って記載されています。他のペアノ公理の文脈ではそうではありませんが、他の公理の文脈では等価です。^{[ 27 ]}具体的には、整列原理は、上記に挙げた最初の2つの公理の文脈で帰納法の公理を含意し、

すべての自然数は、0 または $n + 1のいずれかであり、$ $n$ はある自然数です。

多くの誤った証明に共通する間違いは、 $n - 1$ が一意かつ明確に定義された自然数であると仮定することである。これは他のペアノ公理からは示唆されない性質である。^{[ 27 ]}

注記

↑マット・デヴォス、『数学的帰納法』、サイモン・フレーザー大学
↑ジェラルド・コン・ディアス、「数学的帰納法」、 2013年5月2日にウェイバックマシンにアーカイブ済み、ハーバード大学
↑アンダーソン、ロバート・B. (1979).プログラムの正しさを証明する. ニューヨーク: ジョン・ワイリー・アンド・サンズ. p . 1. ISBN 978-0471033950。
↑スーバー、ピーター。「数学的帰納法」。アールハム大学。2011年5月24日のオリジナルからアーカイブ。 2011年3月26日取得。
↑ 「ユークリッド原論、第7巻、定義1および2」。webspace.ship.edu 。 2026年5月23日取得。
↑アチェルビ、ファビオ（2000年1月1日）。「プラトン：パルメニデス149a7-c3。完全帰納法による証明か？」。精密科学史アーカイブ55（2000）、57-76。
↑ Sriraman, Bharath 編 (2024)、数学的実践の歴史と哲学のハンドブック。第 4 巻、Springer nature reference、Cham: Springer、p. 985、ISBN 978-3-031-40845-8、資料を綿密に読むと、ピタゴラス派が数学的帰納法の原理なしに帰納的証明を持っていたことを示すいくつかの新しい議論が得られます。
↑ラシェッド 1994、62-84頁。
↑数学的知識と実践の相互作用「数学的帰納法による最古の暗黙の証明は、1000年頃、ペルシャの数学者アル・カラジの著作の中で示された」
↑ 「二項定理」 . mathcenter.oxford.emory.edu . 2024年12月2日取得。とはいえ、彼がそれを研究した最初の人物ではない。現在では、935年から1029年まで生きたペルシャの数学者で技術者のアル・カラジがその発見者として認められている。（興味深い豆知識：アル・カラジは、数学的帰納法による議論という強力な概念も導入した。）
↑カッツ（1998）、255ページ
1 2カジョリ (1918) 、p. 197: 「「数学的帰納法」と呼ばれる推論プロセスには、いくつかの独立した起源がある。スイスのヤコブ (ジェームズ) ベルヌーイ、フランスの B. パスカルと P. フェルマー、イタリアの F. マウロリクスにまで遡ることができる。[...] 行間を少し読み解けば、ヒンドゥー教徒やギリシャ人の著作にも、数学的帰納法の痕跡がさらに早く見つかる。例えば、バースカラの「循環法」や、素数の数が無限であるというユークリッドの証明などである。」
↑ラシェッド 1994、p. 62。
↑シモンソン 2000。
↑ラビノビッチ 1970。
↑ 「ある量nが整数または自然数である場合に常に真となる定理を証明することが求められる場合があり、その証明方法は通常次のとおりである。1. n = 1の場合に定理が真であることを証明する。2 . nが与えられた自然数である場合に定理が真であれば、 n が次に大きい整数である場合にも真であることを証明する。したがって、定理は普遍的に真である。…この種の議論は、継続的ソリテスと呼ばれることがある。」(ブール、1849 年頃『論理学入門』（数学的ではない）、40-41 ページ、グラッタン＝ギネス、アイヴァー、ボルネ、ジェラール (1997)『ジョージ・ブール：論理学とその哲学に関する選集』、ビルクハウザー出版、ベルリン、 ISBNに再録 3-7643-5456-9）
↑パース 1881 .
↑シールズ 1997。
↑テッド・サンドストロム著『数学的推論』190ページ、ピアソン、2006年、 ISBN 978-0131877184
↑スムリアン、レイモンド (2014).数学論理入門. ドーバー出版. p. 41. ISBN 978-0486492377。
↑ Buss, Samuel (1986). Bounded Arithmetic . Naples: Bibliopolis.
↑ 「証明：強い帰納法は弱い帰納法と同等である」。コーネル大学。 2023年5月4日取得。
↑ Shafiei, Niloufar. "Strong Induction and Well-Ordering" (PDF) . York University . 2023年5月28日取得.
↑ 「前方後方帰納法 | Brilliant Math & Science Wiki」 brilliant.org 2019年10月23日取得。
↑コーシー、オーギュスタン＝ルイ (1821)。『王立工科大学解析学講義、第1部、代解析』、パリ、2017年10月14日にWayback Machineにアーカイブ済み。算術平均と幾何平均の不等式の証明は457ページ以降に記載されています。
↑コーエン、ジョエル E. (1961). 「数学的証明の本質について」。Opus。『科学におけるランダムウォーク』（RL Weber編）、Crane, Russak & Co.、1973年に再録。
1 2 3 4 5 Öhman, Lars–Daniel (2019 年 5 月 6 日). 「帰納法と整列法は同等か？」 . The Mathematical Intelligencer . 41 (3): 33– 40. doi : 10.1007/s00283-019-09898-4 .

参考文献

導入

Franklin, J. ; Daoud, A. (2011).数学における証明：入門. シドニー：Kew Books. ISBN 978-0-646-54509-7。（第8章）
「数学的帰納法」 .数学百科事典. EMS Press . 2001 [1994].
ヘルメス、ハンス（1973）。数理論理学入門。大学教科書。ロンドン：シュプリンガー。ISBN 978-3540058199ISSN 1431-4657 MR 0345788
クヌース、ドナルド・E. (1997).コンピュータプログラミングの技法、第1巻：基本アルゴリズム（第3 版）. アディソン・ウェスリー. ISBN 978-0-201-89683-1。（第1.2.1節：数学的帰納法、11～21ページ）
コルモゴロフ、アンドレイ・N.、フォミン、セルゲイ・V. (1975).入門実解析. シルバーマン、RA (翻訳、編集). ニューヨーク: ドーバー出版. ISBN 978-0-486-61226-3。（第3.8節：超限帰納法、28～29ページ）

歴史

Acerbi, Fabio (2000年8月) 「プラトン：パルメニデス149a7-c3。完全帰納法による証明か？」 . Archive for History of Exact Sciences . 55 (1): 57–76 . doi : 10.1007/s004070000020 . JSTOR 41134098 . S2CID 123045154 .
Bussey, WH (1917 ) . 「数学的帰納法の起源」。アメリカ数学月報。24 ( 5): 199–207。doi : 10.2307 /2974308。JSTOR 2974308。
カジョリ、フロリアン（1918）。「数学的帰納法」という名称の由来「.アメリカ数学月報. 25 (5): 197– 201. doi : 10.2307/2972638 . JSTOR 2972638 .
ファウラー、D. (1994). 「ギリシャ人は数学的帰納法を使えたのか？実際に使ったのか？」. Physis . 31 : 253–265 .
フロイデンタール、ハンス（1953）。「Zur Geschichte der vollständigen 誘導」。国際科学史アーカイブ。6：17～ 37。
カッツ、ビクター・J. (1998).数学史入門.アディソン・ウェスリー. ISBN 0-321-01618-1。
パース、チャールズ・サンダース( 1881 ) 。「数の論理について」。アメリカ数学ジャーナル。4 ( 1–4 ) : 85–95。doi : 10.2307/2369151。JSTOR 2369151。MR 1507856。再録（CP 3.252–288）、（W 4:299–309）
Rabinovitch, Nachum L. (1970). 「ラビ・レヴィ・ベン・ゲルションと数学的帰納法の起源」. Archive for History of Exact Sciences . 6 (3): 237–248 . doi : 10.1007/BF00327237 . MR 1554128 . S2CID 119948133 .
ラシェド、ロシュディ（ 1972 ）。「数学的帰納法：アル＝カラジー、アッ＝サマーワル」。精密科学史アーカイブ（フランス語）。9 （ 1）：1–21。doi：10.1007 /BF00348537。MR 1554160。S2CID 124040444。
Rashed, R. (1994). 「数学的帰納法：アル＝カラジーとアル＝サマーウアル」『アラビア数学の発展：算術と代数の間』ボストン科学哲学研究シリーズ第 156巻。Springer Science & Business Media。ISBN 9780792325659。
シールズ、ポール（1997）。「パースの算術の公理化」。ハウザー、ネイサン、ロバーツ、ドン・D、エヴラ、ジェームズ・ヴァン（編）『チャールズ・S・パースの論理学研究』所収。インディアナ大学出版局、43-52頁。ISBN 0-253-33020-3MR 1720827 .
Simonson, Charles G. (2000年冬) 「レヴィ・ベン・ゲルションの数学、ラルバグ」(PDF) . Bekhol Derakhekha Daehu . 10 . Bar-Ilan University Press: 5–21 . 2017年10月11日にオリジナル(PDF)からアーカイブ済み。 2019年12月29日取得。
Unguru, S. (1991). 「ギリシャ数学と数学的帰納法」Physis . 28 : 273– 289.
Unguru、S. (1994)。「誘導後のファウリング」。フィシス。31 : 267–272 .
Vacca, G. (1909). 「マウロリコス、数学的帰納法の原理の最初の発見者」 .アメリカ数学会報. 16 (2): 70– 73. doi : 10.1090/S0002-9904-1909-01860-9 . MR 1558845 .
Yadegari, Mohammad (1978). 「アブー・カーミル・シュジャー・イブン・アスラム (850-930) による数学的帰納法の利用」. Isis . 69 ( 2): 259–262 . doi : 10.1086/352009 . JSTOR 230435. S2CID 144112534 .

[1] マット・デヴォス、『数学的帰納法』、サイモン・フレーザー大学

[2] ジェラルド・コン・ディアス、「数学的帰納法」、 2013年5月2日にウェイバックマシンにアーカイブ済み、ハーバード大学

[3] アンダーソン、ロバート・B. (1979).プログラムの正しさを証明する. ニューヨーク: ジョン・ワイリー・アンド・サンズ. p . 1. ISBN 978-0471033950。

[4] スーバー、ピーター。「数学的帰納法」。アールハム大学。2011年5月24日のオリジナルからアーカイブ。 2011年3月26日取得。

[5] 「ユークリッド原論、第7巻、定義1および2」。webspace.ship.edu 。 2026年5月23日取得。

[6] アチェルビ、ファビオ（2000年1月1日）。「プラトン：パルメニデス149a7-c3。完全帰納法による証明か？」。精密科学史アーカイブ55（2000）、57-76。

[7] Sriraman, Bharath 編 (2024)、数学的実践の歴史と哲学のハンドブック。第 4 巻、Springer nature reference、Cham: Springer、p. 985、ISBN 978-3-031-40845-8、資料を綿密に読むと、ピタゴラス派が数学的帰納法の原理なしに帰納的証明を持っていたことを示すいくつかの新しい議論が得られます。

[FOOTNOTERashed199462–84-8] ラシェッド 1994、62-84頁。

[9] 数学的知識と実践の相互作用「数学的帰納法による最古の暗黙の証明は、1000年頃、ペルシャの数学者アル・カラジの著作の中で示された」

[10] 「二項定理」 . mathcenter.oxford.emory.edu . 2024年12月2日取得。とはいえ、彼がそれを研究した最初の人物ではない。現在では、935年から1029年まで生きたペルシャの数学者で技術者のアル・カラジがその発見者として認められている。（興味深い豆知識：アル・カラジは、数学的帰納法による議論という強力な概念も導入した。）

[11] カッツ（1998）、255ページ

[Induction_Bussey-12] 1 2カジョリ (1918) 、p. 197: 「「数学的帰納法」と呼ばれる推論プロセスには、いくつかの独立した起源がある。スイスのヤコブ (ジェームズ) ベルヌーイ、フランスの B. パスカルと P. フェルマー、イタリアの F. マウロリクスにまで遡ることができる。[...] 行間を少し読み解けば、ヒンドゥー教徒やギリシャ人の著作にも、数学的帰納法の痕跡がさらに早く見つかる。例えば、バースカラの「循環法」や、素数の数が無限であるというユークリッドの証明などである。」

[FOOTNOTERashed199462-13] ラシェッド 1994、p. 62。

[FOOTNOTESimonson2000-14] シモンソン 2000。

[FOOTNOTERabinovitch1970-15] ラビノビッチ 1970。

[16] 「ある量nが整数または自然数である場合に常に真となる定理を証明することが求められる場合があり、その証明方法は通常次のとおりである。1. n = 1の場合に定理が真であることを証明する。2 . nが与えられた自然数である場合に定理が真であれば、 n が次に大きい整数である場合にも真であることを証明する。したがって、定理は普遍的に真である。…この種の議論は、継続的ソリテスと呼ばれることがある。」(ブール、1849 年頃『論理学入門』（数学的ではない）、40-41 ページ、グラッタン＝ギネス、アイヴァー、ボルネ、ジェラール (1997)『ジョージ・ブール：論理学とその哲学に関する選集』、ビルクハウザー出版、ベルリン、 ISBNに再録 3-7643-5456-9）

[FOOTNOTEPeirce1881-17] パース 1881 .

[FOOTNOTEShields1997-18] シールズ 1997。

[19] テッド・サンドストロム著『数学的推論』190ページ、ピアソン、2006年、 ISBN 978-0131877184

[20] スムリアン、レイモンド (2014).数学論理入門. ドーバー出版. p. 41. ISBN 978-0486492377。

[Buss:BA-21] Buss, Samuel (1986). Bounded Arithmetic . Naples: Bibliopolis.

[22] 「証明：強い帰納法は弱い帰納法と同等である」。コーネル大学。 2023年5月4日取得。

[yorku-23] Shafiei, Niloufar. "Strong Induction and Well-Ordering" (PDF) . York University . 2023年5月28日取得.

[24] 「前方後方帰納法 | Brilliant Math & Science Wiki」 brilliant.org 2019年10月23日取得。

[25] コーシー、オーギュスタン＝ルイ (1821)。『王立工科大学解析学講義、第1部、代解析』、パリ、2017年10月14日にWayback Machineにアーカイブ済み。算術平均と幾何平均の不等式の証明は457ページ以降に記載されています。

[26] コーエン、ジョエル E. (1961). 「数学的証明の本質について」。Opus。『科学におけるランダムウォーク』（RL Weber編）、Crane, Russak & Co.、1973年に再録。

[Ohman2019-27] 1 2 3 4 5 Öhman, Lars–Daniel (2019 年 5 月 6 日). 「帰納法と整列法は同等か？」 . The Mathematical Intelligencer . 41 (3): 33– 40. doi : 10.1007/s00283-019-09898-4 .

[ 1 ]

[ 2 ]

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

17 ] [

18 ] 、

[

[

22

[ 23 ]

[

[

[ 26 ]

[ 27 ]