[자료구조] 수학적 귀납법

수학적 귀납법

수학적 귀납법 기본형

1. base : P(1)이 참이고
2. step : P(n-1)->P(n)이 참이라면
3. P(n)은 모든 자연수 n에 대하여 참이다.

수학적 귀납법 강한형태

1. base : P(1)이 참이고
2. step : P(1)∧P(2)∧P(3)∧ … ∧P(n-1)->P(n)이 참이라면
3. P(n)은 모든 자연수 n에 대하여 참이다.

수학적 귀납법 쓰임

수학적 귀납법을 이용해 각종 메소드 혹은 함수들의 Trust 의 유무를 따질 수 있다.

---

명제 P -> Q 의 의미

• P -> Q
  • P가 참, Q가 참 -> 전체는 참
  • P가 참, Q가 거짓 -> 전체는 거짓
  • P가 거짓, Q가 참 -> 전체는 참
  • P가 거짓, Q가 거짓 -> 전체는 참

결론 : P가 참일 때는 Q에 따라 전체 명제의 참/거짓이 판별되고, P가 거짓이라면 Q의 참/거짓 에 상관없이 전체 명제는 참이 된다.

---

SUM 재귀 함수의 증명

수학적 귀납법 : sum(x)는 1+2+3+…+x 를 리턴한다. (항상) —

1. P(1)이 참이다 : “sum(1)이 리턴하는 값은 1이다.” 를 증명하면 된다. 실제 코드에 1을 대입하면 1을 리턴할 수 있음
2. P(x-1) -> P(x)이 참이다 : “sum(x-1)이 1+2+3+…+(x-1)을 리턴하면 sum(x)는 1+2+3+…+x 를 리턴한다” 를 증명하면 된다.
3. sum(x)가 x+sum(x-1)를 리턴한다. sum(x-1)의 리턴 값은 1+2+..+(x-1)과 같다고 가정했으므로 sum(x)는 1+2+…+x 를 리턴한다.

결론 : 수학적 귀납법에 의해 sum(x) 재귀함수는 직접 대입하여 실행하지 않고도 Trust 하다고 할 수 있다.