수학적 귀납법

수학적 귀납법: 어떤 명제 P(n) 이 있을 때 모든 자연수 n 에 대해 참임을 증명하는 방법

 - 기본형: P(1) 이 참(BASE)이고, P(n-1)->P(n) 이 참(STEP)이면 P(n) 은 모든 자연수 n 에 대해서 참이다.

 - 강한 형태: P(1) 이 참이고, P(1)∧P(2)∧···∧P(n-1) -> P(n) 이 참이면 P(n) 은 모든 자연수 n 에 대해서 참이다.

수학적 귀납법은 더 어려운 얘기를 쉽게 할 수 있다.

 

❗중요❗ P(n-1)->P(n) ≡ P->Q 의 의미

 - P 가 참, Q 가 참 -> 전제는 참

 - P 가 참, Q 가 거짓 -> 전제는 거짓

 - P 가 거짓, Q 가 참 -> 전제는 참

 - P 가 거짓, Q 가 거짓 -> 전제는 참

P 가 거짓이면 Q 는 '의미 없음'. (참인지 거짓인지와 의미가 있냐 없냐는 것은 독립된 사실)

P->Q 는 각각의 P 와 Q 가 참인지 거짓인지를 따지는 것이 아니라, P->Q 자체가 참이면 되는 것이기 때문.