Mathematical Induction

상위 문서: Mathematical Induction

개요

수학적 귀납법(Proof by Induction)은 자연수에 대한 명제를 증명할 때 주로 사용되는 증명 방법이다.

Principle of Mathematical Induction

Figure 1. Proofs by Induction

수학적 귀납법은 자연수에 대한 명제를 증명할 때 주로 사용되는 추론 규칙이다. 이의 목표는 $\mathrm{\forall }n.P(n)$을 증명하는 것, 즉 모든 자연수 n에 대해 명제 $P(n)$이 참임을 증명하는 것이다. 귀납법은 다음 두 단계로 나뉘어진다:

1. Basis (기초 단계): $P(0)$을 먼저 증명한다.
2. Induction Step (귀납 단계): $\mathrm{\forall }n.P(n)\to P(n+1)$임을 증명한다.

위 두 단계를 fitch-style 형식으로 정리하면 figure 1과 같은 꼴이 된다.

${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$