誤った数学的帰納法を使うと…3!=3
数学的帰納法とその誤解
数学的帰納法をExcelのシートで説明してみる
に続いて、数学的帰納法の原理の命題を誤解して使用するとおかしな結果が導かれる簡単な例を考えてみた。
数学的帰納法
($P(1) \land \forall k \in \mathbb{N};(P(k) \Longrightarrow P(k+1)) $)
$ \qquad \Longrightarrow \forall n\in \mathbb{N};P(n)$
数学的帰納法
- $P(1)$
- どんな自然数$k$に対しても$P(k) \Longrightarrow P(k+1) $
が成立するならば、
任意の自然数$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)$
誤った数学的帰納法
- $P(1)$
- ある自然数$k$に対して$P(k) \Longrightarrow P(k+1) $
が成立するならば、
任意の自然数$n$に対して$P(n)$
0以上の整数に対して階乗を定義
$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$
命題「$n!=n$」を考える
命題$P(n) $を「$n!=n$」とする。
$n=1$のとき
$1!=1\times 0!=1\times 1=1 $
$\therefore P(1)$
$n=1+1=2$のとき
$(1+1)!=2!=2 \times 1!$
$n=1$ のとき$1!=1 $だから$P(1)$より
$(1+1)!=2 \times 1=2=1+1$
$\therefore P(1+1)$
$P(1) \Longrightarrow 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 $としたものは誤りである。
