[이산수학]수학적 귀납법(Mathematical Induction)

수학적 귀납법 (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)이 참이라는 가정으로 시작해서 풀면 안된다!