WIIS

教材一覧
教材一覧
教材検索
DEFINITION OF REAL NUMBER

完全帰納法の原理(強数学的帰納法の原理)

目次

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有

完全帰納法の原理

復習になりますが、数学的帰納法による証明とは、自然数\(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*}が成り立つことを示すというものです。

数学的帰納法が証明方法として有効であることの根拠は以下の命題であり、これを数学的帰納法の原理と呼びました。

命題(数学的帰納法の原理)
自然数集合\(\mathbb{N} \)の部分集合\(A\)が以下の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*}を満たす場合には、\begin{equation*}
A=\mathbb{N} \end{equation*}が成り立つ。

数学的帰納法の原理は以下の命題と必要十分です。これを完全帰納法の原理(the principle of complete induction)や強数学的帰納法の原理(the strong principle of mathematical induction)などと呼びます。

命題(完全帰納法の原理)
自然数集合\(\mathbb{N} \)の部分集合\(A\)が以下の2つの条件\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*}が成り立つことは、数学的帰納法の原理が成り立つための必要十分条件である。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

 

完全帰納法による証明

先の命題は完全帰納法による証明(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) \quad \cdots (1)
\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) \quad \cdots (2)
\end{equation}が成り立つことを示すというものです。特に\(\left( 2\right) \)は、自然数\(k\)を任意に選んだとき、\(k\)以下の任意の自然数\(n\)について\(P\left( n\right) \)が成り立つという仮定のもとで\(P\left( k+1\right) \)が成り立つことを示す作業に相当します。いずれにせよ、\(\left( 1\right) \)と\(\left(2\right) \)がともに真であることを証明できたとしましょう。これは、先の命題中の\(A\)に相当する集合の任意の要素\(k\in A\)について\(P\left( k\right) \)が成り立つことが示されたということです。ただ、先の命題より\(A=\mathbb{N} \)という関係が成り立つため、以上の証明により、\(P\left( k\right) \)が任意の自然数\(k\in \mathbb{N} \)について成り立つことを示したことになります。完全帰納法の原理は強数学的帰納法(proof by strong mathematical induction)とも呼ばれます。

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

例(完全帰納法による証明)
\(2\)以上の自然数\(n\in \mathbb{N} \)を任意に選んだとき、\(n\)は素数の積として一意的に表すことができることを証明します。まず、\(n=2\)の場合、与えられた主張は、\begin{equation*}2\text{は素数の積として一意的に表すことができる}
\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\)は素数の積として一意的に表すことができることが明らかになりました。以上で証明が完了しました。

 

演習問題

問題(完全帰納法による証明)
数列\(\left\{ x_{n}\right\} \)が、\begin{equation*}\left\{
\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*}という関係が成り立つことを完全帰納法による証明によって示してください。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

数学的帰納法
数学的帰納法の原理

数学的帰納法とは、自然数 n に関する命題 P(n) が全ての自然数 n に対して成り立つことを示す手法の1つですが、この証明方法が有効であることの根拠(数学的帰納法の原理)を解説します。

DISCUSSION

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録