数学的帰納法の原理（弱数学的帰納法の原理）

数学的帰納法の原理

復習になりますが、実数空間\(\mathbb{R} \)の部分集合\(A\)が帰納集合であることとは、以下の2つの条件\begin{eqnarray*}&&\left( a\right) \ 1\in A \\
&&\left( b\right) \ \forall x\in \mathbb{R} :\left( x\in A\Rightarrow x+1\in A\right)
\end{eqnarray*}が成り立つこととして定義されます。さらに、\(\mathbb{R} \)におけるすべての帰納的集合からなる集合族を\(\left\{ A_{\lambda }\right\} _{\lambda \in \Lambda} \)で表記するとき、\begin{equation*}\mathbb{N} =\bigcap\limits_{\lambda \in \Lambda }A_{\lambda }\end{equation*}を満たすものとして自然数集合\(\mathbb{N} \)を定義しました。加えて、\(\mathbb{N} \)自身もまた帰納集合であることを示しました。

自然数集合の部分集合\(A\subset \mathbb{N} \)を任意に選びます。ただし、これは以下の2つの条件\begin{eqnarray*}&&\left( a\right) \ 1\in A \\
&&\left( b\right) \ \forall k\in \mathbb{N} :\left( k\in A\Rightarrow k+1\in A\right)
\end{eqnarray*}を満たすものとします。\(\mathbb{N} \subset \mathbb{R} \)であることを踏まえると、上の2つの条件が成り立つことは\(A\)が帰納的集合であることを意味します。\(\mathbb{N} \)はすべての帰納的集合の共通部分であるため、\(\mathbb{N} \)は任意の帰納的集合の部分集合です。\(A\)は帰納的集合であるため、このとき、\begin{equation*}\mathbb{N} \subset A\end{equation*}が成り立ちます。一方、仮定より\begin{equation*}
A\subset \mathbb{N} \end{equation*}であるため、結局、\begin{equation*}
A=\mathbb{N} \end{equation*}であることが示されました。これを数学的帰納法の原理（the principle of mathematical induction）や弱数学的帰納法の原理（the principle of weak mathematical induction）などと呼びます。

数学的帰納法による証明

先の命題は数学的帰納法による証明（proof by mathematical induction）の根拠になります。数学的帰納法とは、自然数\(n\)に関する主張\begin{equation*}P\left( n\right)
\end{equation*}が任意の自然数\(n\in \mathbb{N} \)に関して成り立つことを示すための手法であり、具体的には、まず、\(n=1\)の場合の主張\begin{equation*}P\left( 1\right)
\end{equation*}が真であることを示した上で、さらに自然数\(k\in \mathbb{N} \)を任意に選んだ上で、\begin{equation*}P\left( k\right) \Rightarrow P\left( k+1\right)
\end{equation*}が成り立つことを示すというものです。なぜ、この手法が有効なのでしょうか。順番に説明します。

改めて整理すると、数学的帰納法とは、以下の全称命題\begin{equation}
\forall n\in \mathbb{N} :P\left( n\right) \quad \cdots (1)
\end{equation}が真であることを示すために、以下の2つの命題\begin{eqnarray*}
&&\left( a\right) \ P\left( 1\right) \\
&&\left( b\right) \ \forall k\in \mathbb{N} :P\left( k\right) \Rightarrow P\left( k+1\right)
\end{eqnarray*}が真であることを示す、というものです。\(\left( a\right) \)と\(\left( b\right) \)がともに真であることを証明できたとします。集合\(A\subset \mathbb{N} \)を、\begin{equation*}A=\left\{ n\in \mathbb{N} \ |\ P\left( n\right) \right\}
\end{equation*}と定義したとき、\(\left(a\right) \)と\(\left( b\right) \)が真であることは、\begin{eqnarray*}&&\left( a\right) \ 1\in A \\
&&\left( b\right) \ \forall k\in \mathbb{N} :k\in A\Rightarrow k+1\in A
\end{eqnarray*}がともに真であることを意味します。すると、数学的帰納法の原理より、\begin{equation*}
A=\mathbb{N} \end{equation*}を得ますが、これと\(A\)の定義より、\begin{equation*}\mathbb{N} =\left\{ n\in \mathbb{N} \ |\ P\left( n\right) \right\} \end{equation*}すなわち、\begin{equation*}
\forall n\in \mathbb{N} :P\left( n\right)
\end{equation*}を得ます。これは\(\left(1\right) \)に他なりません。以上の理由により、\(\left( a\right) \)と\(\left( b\right) \)が真であることを示せば\(\left( 1\right) \)が真であることを示したことになることが明らかになりました。

数学的帰納法による証明の例をいくつか提示します。

演習問題