数学的帰納法

数学的帰納法(mathmatical induction)

述語/命題関数$ P がとる値の範囲が自然数の場合の帰納法による証明をする場合、数学的帰納法と呼ばれる

$ P(n) \quad (n \in \N)

自然数は0はじまり

1でもOK？

P(n)は述語/命題関数

述語(property)

命題関数(propositional logic)

n = 0, 1, ... ($ n \in \N )

m = 1, 2, ...

(1) n = 0のとき、P(0)が成り立つ

(2) もし任意のmについて、P(m)が成り立つならば、P(m + 1)も成り立つ

(1)、(2)の両方が真であるならば、すべてのnについてP(n)が成り立つ

(1)が命題関数の基底の場合

きちんとした論理式にすると以下になる。

$ (P(0) \land (\forall m \in \omega.\ P(m) \to P(m + 1 )) \to \forall n \in \omega.\; P(n)

$ \omega : 0から始まる自然数の集合

ChatGPTに聞いた結果だけど多分あってるはず

より一般的なものは

確認用

Q. 数学的帰納法

Q. 数学的帰納法による証明の具体例