完全帰納法の原理
復習になりますが、数学的帰納法による証明とは、自然数\(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*}が成り立つことを示すというものです。
数学的帰納法が証明方法として有効であることの根拠は以下の命題であり、これを数学的帰納法の原理と呼びました。
&&\left( b\right) \ \forall k\in \mathbb{N} :\left( k\in A\Rightarrow k+1\in A\right)
\end{eqnarray*}を満たす場合には、\begin{equation*}
A=\mathbb{N} \end{equation*}が成り立つ。
数学的帰納法の原理は以下の命題と必要十分です。これを完全帰納法の原理（the principle of complete induction）や強数学的帰納法の原理（the strong principle of mathematical induction）などと呼びます。
&&\left( b\right) \ \forall k\in \mathbb{N} :\left[ \left( \forall n\in \mathbb{N} :\left( n\leq k\Rightarrow n\in A\right) \right) \Rightarrow k+1\in A\right] \end{eqnarray*}を満たす場合には、\begin{equation*}
A=\mathbb{N} \end{equation*}が成り立つことは、数学的帰納法の原理が成り立つための必要十分条件である。
完全帰納法による証明
先の命題は完全帰納法による証明（proof by complete 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*}\left[ \forall n\in \mathbb{N} :\left( n\leq k\Rightarrow P\left( n\right) \right) \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} :\left[ \left( \forall n\in \mathbb{N} :\left( n\leq k\Rightarrow P\left( n\right) \right) \right) \Rightarrow
P\left( k+1\right) \right]
\end{eqnarray*}が真であることを示す、というものです。特に\(\left( b\right) \)は、自然数\(k\)を任意に選んだとき、\(k\)以下の任意の自然数\(n\)について\(P\left( n\right) \)が成り立つという仮定のもとで\(P\left( k+1\right) \)が成り立つことを示す作業に相当します。さて、\(\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} :\left[ \left( \forall n\in \mathbb{N} :\left( n\leq k\Rightarrow n\in A\right) \right) \Rightarrow k+1\in A\right]
\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) \)が真であることを示したことになることが明らかになりました。
完全帰納法による証明の利用例を提示します。
\end{equation*}となりますが、\(2\)は素数\(2\)と一致するため主張が成り立ちます。\(2\)以上の自然数\(k\in \mathbb{N} \)を任意に選んだ上で、\(n\leq k\)を満たす任意の番号\(n\in \mathbb{N} \)について主張が成り立つものと仮定します。つまり、自然数\begin{equation}2,3,4,\cdots ,k\text{はそれぞれ素数の積として一意的に表すことができる} \quad \cdots (1)
\end{equation}ことを仮定するということです。このとき、自然数\(k+1\)が素数の積として一意的に表すことができることを示すことに成功すれば、完全帰納法の原理より、\(2\)以上の任意の自然数\(n\)について主張が成り立つことを示したことになります。さて、\(k+1\)が素数である場合、\(k+1\)は素数\(k+1\)と一致するため主張が成り立ちます。\(k+1\)が素数ではない場合（つまり\(k+1\)が合成数である場合）、素数の定義より、\(k+1\)は\(1\)や\(k+1\)とは異なる素因数を持ちます。そこで、\(k+1\)の素因数の中で最小のものを\(p\)で表記するのであれば、\begin{equation}k+1=p\times N \quad \cdots (2)
\end{equation}という関係を満たす自然数\(N\)が存在します。明らかに\(N<k\)であるため、仮定\(\left( 1\right) \)より、\(N\)は素数の積として一意的に表すことができます。以上の事実と\(\left( 2\right) \)および\(p\)が\(k+1\)の素因数であることから、\(k+1\)は素数の積として一意的に表すことができることが明らかになりました。以上で証明が完了しました。
演習問題
\begin{array}{l}
x_{1}=1 \\
x_{2}=2 \\
x_{3}=6 \\
x_{n}=\left( n^{3}-3n^{2}+2n\right) x_{n-3}\quad \left( n\geq 4\right)\end{array}\right.
\end{equation*}と再帰的に定義されているものとします。このとき、任意の\(n\in \mathbb{N} \)について、\begin{equation*}x_{n}=n!
\end{equation*}という関係が成り立つことを完全帰納法による証明によって示してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】