数学的帰納法の定義
数学的帰納法
自然数 $n$ に関する命題を $P(n)$ とする.
以下が成り立つならば, 任意の $n \in \mathbb{N}$ について, $P(n)$ が真である;
- $P(1)$ が真である
- $n \in \mathbb{N}$ について, $P(n)$ が真ならば, $P(n+1)$ も真である
例えば, $P(n): n +1 \in \mathbb{N}$ は
- $P(1): 2 \in \mathbb{N}$ は真です。
- $P(n): n+1 \in \mathbb{N}$ が真と仮定します。命題 $P(n+1)$ について, $(n+1)+1$ は $n+1 \in \mathbb{N}$ かつ $1 \in \mathbb{N}$ が言えるから, $(n+1)+1 = n+2 \in \mathbb{N}$ が真と言えます。
数学的帰納法によって, 全ての自然数 $n$ について命題 $P(n)$ は真です！
