WIIS

実数の定義

数学的帰納法の原理(弱数学的帰納法の原理)

目次

Mailで保存
Xで共有

数学的帰納法の原理

復習になりますが、実数空間\(\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)などと呼びます。

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

 

数学的帰納法による証明

先の命題は数学的帰納法による証明(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) \)が真であることを示したことになることが明らかになりました。

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

例(数学的帰納法による証明)
自然数\(n\in \mathbb{N} \)を任意に選んだとき、\begin{equation*}1+2+3+\cdots +n=\frac{n\left( n+1\right) }{2}
\end{equation*}が成り立つことを証明します。\(n=1\)の場合、与えられた主張は、\begin{equation*}1=\frac{1\left( 1+1\right) }{2}
\end{equation*}となりますが、右辺は\(1\)であるため、これは明らかに成り立ちます。自然数\(k\in \mathbb{R} \)を任意に選んだ上で、\(n=k\)の場合に主張が成り立つものと仮定します。つまり、\begin{equation}1+2+3+\cdots +k=\frac{k\left( k+1\right) }{2} \quad \cdots (1)
\end{equation}が成り立つことを仮定するということです。このとき、\begin{eqnarray*}
1+2+3+\cdots +k+\left( k+1\right) &=&\frac{k\left( k+1\right) }{2}+\left(
k+1\right) \quad \because \left( 1\right) \\
&=&\frac{k\left( k+1\right) }{2}+\frac{2\left( k+1\right) }{2} \\
&=&\frac{\left( k+1\right) \left( k+2\right) }{2}
\end{eqnarray*}となるため、\(n=k+1\)についても主張が成り立つことが明らかになりました。したがって、数学的帰納法により、任意の自然数\(n\)について主張が成り立つことが示されました。
例(数学的帰納法による証明)
自然数\(n\in \mathbb{N} \)を任意に選んだとき、\begin{equation*}1+2+2^{2}+\cdots +2^{n-1}=2^{n}-1
\end{equation*}が成り立つことを証明します。\(n=1\)の場合、与えられた主張は、\begin{equation*}2^{1-1}=2^{1}-1
\end{equation*}すなわち、\begin{equation*}
1=1
\end{equation*}となりますが、これは明らかに成り立ちます。自然数\(k\in \mathbb{R} \)を任意に選んだ上で、\(n=k\)の場合に主張が成り立つものと仮定します。つまり、\begin{equation}1+2+2^{2}\cdots +2^{k-1}=2^{k}-1 \quad \cdots (1)
\end{equation}が成り立つことを仮定するということです。このとき、\begin{eqnarray*}
1+2+2^{2}+\cdots +2^{k}+2^{k+1} &=&\left( 1+2+\cdots +2^{k}\right) +2^{k+1}
\\
&=&\left( 2^{k}-1\right) +2^{k+1}\quad \because \left( 1\right) \\
&=&2^{k+2}-1
\end{eqnarray*}となるため、\(n=k+1\)の場合についても主張が成り立つことが明らかになりました。したがって、数学的帰納法により、任意の自然数\(n\)について主張が成り立つことが示されました。

 

演習問題

問題(数学的帰納法の原理)
自然数\(n\in \mathbb{N} \)を任意に選んだとき、\begin{equation*}1^{2}+2^{2}+3^{2}+\cdots +n^{2}=\frac{n\left( n+1\right) \left( 2n+1\right)
}{6}
\end{equation*}が成り立つことを証明してください。

解答を見る

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

問題(数学的帰納法の原理)
自然数\(n\in \mathbb{N} \)を任意に選んだとき、\begin{equation*}7^{n}-4^{n}
\end{equation*}が\(3\)の倍数であることを証明してください。
解答を見る

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

問題(ベルヌーイの不等式)
任意の非負の整数\(n=0,1,2,3,\cdots \)について、以下の主張\begin{equation*}\forall x\in \mathbb{R} :\left[ x\geq -1\Rightarrow \left( 1+x\right) ^{n}\geq 1+nx\right] \end{equation*}が成り立つことを示してください。これをベルヌーイの不等式(Bernoulli’s inequality)と呼びます。

証明

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

関連知識

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

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