この原理からもともとの形の数学的帰納法が導かれることは，次のようにして示せる。帰納法の仮定 1., 2. を満たす論理式 P(n) が与えられたとする。自然数の部分集合 A を A = { n ∈ N: ¬ P(n) } によって定める。この A が空集合であるということを示したい。そうでないと仮定すると、Aに属する最小の自然数 a を取ることができるが、P(0)は成り立っていることから a は0でない。従って、ある自然数 b について a = b + 1となっているが、a は A に属する最小の自然数であったということから、b ∉ A であり、P(b) は成り立つことになる。帰納法の仮定から P(a) も成り立つことになり、これは矛盾である。

逆に、「n 以下の任意の自然数 k について k ∉ A」という形の命題 P(n) を考えることで、数学的帰納法から上の原理を導くことができる。A を自然数のある集合とし、A に属する最小の自然数が存在しないと仮定する。もし P (0) が成り立たないと、0 が A に属する最小の自然数となって仮定に反するから、P(0) は成り立つ。P(n) が成り立つとし、もし P (n + 1) が成り立たないとすると、n + 1 が A の最小の自然数となって仮定に反するから、P(n + 1) も成り立つ。よって数学的帰納法により A は空となる。
超限帰納法

上記の形で自然数について定式化された数学的帰納法は、任意の整列集合に対して次のように一般化することができる。この一般化を超限帰納法 (ちょうげんきのうほう、英: transfinite induction)という。任意濃度の集合は選択公理と同値な整列可能定理により整列順序を持つとすることができるので、選択公理を含む公理系であれば超限帰納法は任意濃度の集合に対して成立すると主張できる。
超限帰納法
(A , ≤) を整列集合とし、P(x) を A 上で定義された命題関数とする。もし次の条件が成立するならば、任意の x ∈ A について P(x) は真である。
条件
a を A の任意の元とする。x < a を満たす A の全ての元 x について P(x) が真ならば、P(a) も真である。

ただし、"<" は a < b ⇔ ( a ≤ b ∧ a ≠ b) で定義される二項関係とする。
証明

A を全体集合とする。A の各元 a に対して A(a) = { x∈A  |  x < a } とし、A1 = { x∈A  |  P(x) } とする。そのとき、超限帰納法の条件は ∀ a ∈ A ( A ( a ) ⊆ A 1 ⇒ a ∈ A 1 ) {\displaystyle \forall a\in A(A(a)\subseteq A_{1}\Rightarrow a\in A_{1})} (1)

と同値である。また、補集合に関する法則から (1) は ∀ a ∈ A ( A ( a ) ∩ A 1 c = ∅ ⇒ a ∈ A 1 ) {\displaystyle \forall a\in A(A(a)\cap A_{1}^{c}=\varnothing \Rightarrow a\in A_{1})} (2)

と同値である。これらの条件が満たされているという前提の下で、A1 = A すなわち A1c = ∅ が成り立つことを示せばよい。

いま、A1c ≠ ∅と仮定して矛盾を導く。背理法の仮定と整列集合の定義より、min A1c = a が存在する。この a について、最小元の定義より A(a)∩A1c = ∅ が成り立つので、 (2) より a ∈ A1 もまた成り立つ。しかし、これは a ∈ A1c であることに反する。（証明終）
整礎帰納法詳細は「整礎帰納法」を参照

無限下降列が存在しない二項関係を整礎関係という。整礎関係が定義された集合に対して次が成り立つ。これを整礎帰納法（英: well-founded induction）という。R を集合 A 上の整礎関係とし、P(x) を A の元 x に関する命題とする。もし次が成立するならば、任意の x ∈ A について P(x) は真である。任意の a ∈ A をとる。x R a なる任意の A の元 x について P(x) が真ならば、P(a) も真である。

超限帰納法は整礎帰納法の特殊な場合である。特に、超限帰納法においては、任意の空でない部分集合に最小元が存在する、という性質が、整礎帰納法においては、任意の空でない部分集合に極小元が存在する、という性質に対応している。
ハゲ頭のパラドックス

数学的帰納法を意図的に誤用したジョークとして、次のようなものがある[5]：髪の毛が一本もない人はハゲである。ハゲの人に髪の毛を一本足してもやっぱりハゲである[注 4]。よって数学的帰納法により、全ての人はハゲている。

もちろんこの「証明」には理論上の根本的な問題点がある。この「証明」の問題点は、「ハゲ」の定義を厳密に毛が何本以下であるかで与えることができない点、もしくは「ハゲ」を定義できたとして、任意の「ハゲ」に髪の毛を一本足したときに、必ず「ハゲ」になるわけではない点にある。以上のような論法の起源は、古代ギリシャの哲学者ミレトスのエウブリデス (en) が作ったとされるハゲ頭のパラドックス (Paradox of the Bald Man)[6]に帰せられる。これは砂山のパラドックスの起源としても知られる。

前述のジョークにはさまざまなバリエーションがあるが、いずれも「少量の増加程度では大差ない。よって数学的帰納法より沢山の増加でも差はない」という誤謬を利用している。
歴史

初期の例としては、プラトンによるパルメニデス（紀元前 370年）において暗黙に帰納法を使用した証明がみられる[7]。また数学的帰納法としての痕跡は、素数が無限個あることを示したユークリッドの証明や、バースカラ2世による "cyclic method（英語版）[8] に見ることができる。通常とは逆に、パラメータとなる自然数が減少していく逐次的な論法は、砂山のパラドックスにみられる。つまり、10,000粒の砂粒が砂山を形成し、そこから一粒の砂を取り除いても砂山が残るならば、一粒だけ残った砂(或いは全ての粒を取り去った後)でもなお砂山を形成するといえる。

等差数列について暗黙に数学的帰納法を用いた証明は、紀元 1000年ごろにアル＝カラジ（英語版）による "al-Fakhri" に扱われている。アル＝カラジは二項定理やパスカルの三角形を示すのに数学的帰納法を用いた。

しかし、これらの古代の数学者たちは帰納法の仮定を明示することはしていない。別の似た例としては(Freudenthal が注意深く示したように、Vacca が著したものとは対立するが)、フランチェスコ・マウロリコ（英語版）が 1575年の著作 "Arithmeticorum libri duo" にて最初の n 個の奇数の和が n2 に等しいことを示す際にこの技術を用いている。明示された形での数学的帰納法の原理はパスカルがその著作 "Traite du triangle arithmetique" (1655)にて与えた。