수학적 귀납법

수학적 귀납법 (Mathematical Induction) 은 다음과 같습니다.

$\mathbb{N}$의 부분집합 $S$가 $1 \in S$이고, 임의의 $n \in S$에 대하여 $n^{+} \in S$이면 ($n + 1 \in S$이면) $\mathbb{N} \subset S$이다.
(즉, $S = \mathbb{N}$)

$\mathbb{N}$은 자연수 집합 표기 입니다.
수학적 귀납법은 공리이기 때문에 증명 없이 받아드립니다. 다른 증명을 위한 템플릿으로 볼 수 있습니다.
통상적으로 명제 $P(n)$이 참인 $n$의 집합을 $S$로 잡고, 다음과 같이 수학적 귀납법을 사용합니다.

$P(1)$이 참이고, 임의의 $n \in \mathbb{N}$에 대하여 $P(n)$이 참일 때 $P(n + 1)$도 참이라면, 모든 $n \in \mathbb{N}$에 대하여 $P(n)$이 참이다.

명제 $P(n)$이 $1$부터 $k$까지는 성립하지 않고 $k + 1$ 이상에서만 성립하더라도 $Q(n) = P(n + k)$로 평행이동 시키면 $Q(n)$이 성립하는게 자연수 집합 전체임을 알 수 있습니다.
자연수의 정렬 원리 와 동치명제 입니다.