수학적 귀납법 (Mathematical Induction)은 다음과 같은 단계를 거친다.
(a) P(No)은 참이다.
(b) 어떤 k ≥ No 에 대하여 P(k)가 참이면, P(k+1)도 반드시 참이다.
그러면 모든 N ≥ No 에 대하여 P(N)이 참이다.
(a)를 기본단계(basis step)이라고 하며 쉬운 단계이다.
(b) 단계에서는 P(k)가 참이면 P(k+1)도 참임을 보이면 되는데,
이 단계를 귀납단계(induction step)라고 하며 어려운 단계이다.
주의할 점!
P(k+1)이 참이라는 가정으로 시작해서 풀면 안된다!
