数学的帰納法が正しいことを証明する。
つまり、
定理
自然数ｎについての命題Ｐ(ｎ)が与えられているとする。もし、
（１）Ｐ(１)が真であること、
（２）各自然数ｋについて、
でＰ（ｋ）が真ならばＰ(ｋ＋１)も真であること、
が示されるならば、すべての自然数ｎについて、Ｐ(ｎ)は真である。
を証明する。
ここで、Ｐ(１)とは、ｎ＝１のときのＰ(ｎ)のことである。
同様に、Ｐ(ｋ)はｎ＝ｋのときのＰ(ｎ)のこと。
この定理のことを、私たちは数学的帰納法と呼んでいる。
以下の証明は、内田伏一著『集合と位相』（裳華房）に載っている「超限帰納法」の証明を参考にした。
＜定理の証明＞
（１），（２）が示されているのに、命題Ｐ(ｎ)が偽であるような自然数ｎが存在する、と仮定する。
命題Ｐ(ｎ)が偽であるようなｎのうち最小のものをＮとする。
すると、
ｎ＜ＮならばＰ(ｎ)は真 …(＊)
である。
また、（１）が示されているから、Ｎ≠１である。
（ｎ＝１のときＰ(１)は真、ｎ＝ＮのときＰ(ｎ)は偽だから、Ｎ＝１なわけがない。）
よって、Ｎ＞１である。
したがって、Ｎ－１＞０となり、Ｎ－１は自然数である。
さて、
当たり前だけどＮ－１＜Ｎである。
これと(＊)より、Ｐ(Ｎ－１)は真である。
（Ｐ(ｎ)は自然数についての命題だから、Ｎ－１＝０だとＰ(Ｎ－１)は意味をなさない。
しかし、さっき確認したようにＮ－１は自然数だから問題ない）
（２）が示されているから、ｋ＝Ｎの場合を考えて、Ｐ(Ｎ)も真である。
これは、Ｎの「命題Ｐ(ｎ)が偽であるようなｎ」という性質に矛盾する。□
高校数学では見慣れない論法もでてきて、ちょっと難しい証明だが、よく考えれば分らなくはないと思う。もう少し詳しく説明した方がいい部分もあったかもしれないが、あまりごちゃごちゃすると、論理の流れの全体像が見えにくくなるので、「（ ）」で書いた箇所程度にした。
いずれにせよ、数学的帰納法が正しいことは、自然数の性質と背理法によって証明できる。
ここで使った自然数の性質は、多少難しい話になるが、「自然数の部分集合には必ず最小元が存在する」という性質である。証明中「Ｎの存在」を保証するのにこの性質を使っている。
つまり、
定理
自然数ｎについての命題Ｐ(ｎ)が与えられているとする。もし、
（１）Ｐ(１)が真であること、
（２）各自然数ｋについて、
でＰ（ｋ）が真ならばＰ(ｋ＋１)も真であること、
が示されるならば、すべての自然数ｎについて、Ｐ(ｎ)は真である。
を証明する。
ここで、Ｐ(１)とは、ｎ＝１のときのＰ(ｎ)のことである。
同様に、Ｐ(ｋ)はｎ＝ｋのときのＰ(ｎ)のこと。
この定理のことを、私たちは数学的帰納法と呼んでいる。
以下の証明は、内田伏一著『集合と位相』（裳華房）に載っている「超限帰納法」の証明を参考にした。
＜定理の証明＞
（１），（２）が示されているのに、命題Ｐ(ｎ)が偽であるような自然数ｎが存在する、と仮定する。
命題Ｐ(ｎ)が偽であるようなｎのうち最小のものをＮとする。
すると、
ｎ＜ＮならばＰ(ｎ)は真 …(＊)
である。
また、（１）が示されているから、Ｎ≠１である。
（ｎ＝１のときＰ(１)は真、ｎ＝ＮのときＰ(ｎ)は偽だから、Ｎ＝１なわけがない。）
よって、Ｎ＞１である。
したがって、Ｎ－１＞０となり、Ｎ－１は自然数である。
さて、
当たり前だけどＮ－１＜Ｎである。
これと(＊)より、Ｐ(Ｎ－１)は真である。
（Ｐ(ｎ)は自然数についての命題だから、Ｎ－１＝０だとＰ(Ｎ－１)は意味をなさない。
しかし、さっき確認したようにＮ－１は自然数だから問題ない）
（２）が示されているから、ｋ＝Ｎの場合を考えて、Ｐ(Ｎ)も真である。
これは、Ｎの「命題Ｐ(ｎ)が偽であるようなｎ」という性質に矛盾する。□
高校数学では見慣れない論法もでてきて、ちょっと難しい証明だが、よく考えれば分らなくはないと思う。もう少し詳しく説明した方がいい部分もあったかもしれないが、あまりごちゃごちゃすると、論理の流れの全体像が見えにくくなるので、「（ ）」で書いた箇所程度にした。
いずれにせよ、数学的帰納法が正しいことは、自然数の性質と背理法によって証明できる。
ここで使った自然数の性質は、多少難しい話になるが、「自然数の部分集合には必ず最小元が存在する」という性質である。証明中「Ｎの存在」を保証するのにこの性質を使っている。