数学的帰納法をExcelのシートで説明してみる
に続いて、数学的帰納法の原理の命題を誤解して使用するとおかしな結果が導かれる簡単な例を考えてみた。
($P(1) \land \forall k \in \mathbb{N};(P(k) \Longrightarrow P(k+1)) $)
$ \qquad \Longrightarrow \forall n\in \mathbb{N};P(n)$
が成立するならば、
任意の自然数$n$に対して$P(n)$
を誤解していると思われる
($P(1) \land $$ \exists $$ k \in \mathbb{N};(P(k) \Longrightarrow P(k+1)) $)
$ \qquad \Longrightarrow \forall n\in \mathbb{N};P(n)$
が成立するならば、
任意の自然数$n$に対して$P(n)$
$n$を0以上の整数とする。$n!$を以下のように定義して、$n$の階乗と呼ぶ。
$n!:=$$\begin{eqnarray} \left\{ \begin{array}{l} 1 \qquad\qquad\qquad \cdots n=0\\ n\times (n-1)! \qquad\cdots n>0 \end{array} \right. \end{eqnarray}$
例
$0!=1 $
$1!=1 \times 0!=1$
$2!=2 \times 1!=2$
$3!=3 \times 2!=6$
$\cdots$
命題$P(n) $を「$n!=n$」とする。
$1!=1\times 0!=1\times 1=1 $
$\therefore P(1)$
$(1+1)!=2!=2 \times 1!$
$n=1$ のとき$1!=1 $だから$P(1)$より
$(1+1)!=2 \times 1=2=1+1$
$\therefore P(1+1)$
つまり、これは$k=1$に対して$n=k$で$P(k)$が成り立つときに、
$P(k+1)$つまり、「$(k+1)!=k+1$」を示したことになる。
$\therefore$「$1$という自然数$k$に対して、$P(k) \Longrightarrow P(k+1) $」
ここで、誤った数学的帰納法が正しいとすると、
「ある自然数$k$に対して$P(k) \Longrightarrow P(k+1) $ 」
が成り立つので、「任意の自然数$n$に対して$P(n)$」となり、
$P(3)$つまり「$3!=3$」も成り立つことになってしまう。
もちろん実際には、$3!=6 \neq 3$なので、$P(3)$は成り立たないので矛盾する。
数学的帰納法
($P(1) \land \forall k \in \mathbb{N};(P(k) \Longrightarrow P(k+1)) $)
$ \qquad \Longrightarrow \forall n\in \mathbb{N};P(n)$
の$P(k)$の前の$\forall $を$\exists $としたものは誤りである。