수학적 귀납법과 재귀, 분할 정복

수학적 귀납법

 

 

수학 증명 기법중 하나

 

프로그래밍에서 자주 쓰이니 꼭 알아두자

 

증명방법

 

1. 기본 단계 : 시작점 P(0)이 참임을 증명
2. 귀납 가정 : 임의의 자연수 K에 대해 P(K)가 참일때, P(K + 1)도 참일 것이라는 가설을 세움. P(K) → P(K + 1)
3. 귀납 단계 : 이 가설이 참임을 증명
4. 결론 : 그럼 P(0)이 참이니 P(1)도 참이고, P(1)이 참이니 P(2)도 참.  이렇게 연쇄적으로 참이 돼서 모든 자연수 n에 대하여 P(n)이 참인것이 증명이됨.

ex) 도미노게임을 이용한 예시

 

1. 첫번째 도미노와 두번째 도미노를 일정한 간격에 두면 쓰러진다고 증명
2. 마찬가지로 k번째 도미노와 k+1번째 도미노도 똑같을 거라 가정
3. 실제로 된다는 걸 증명
4. 첫번째 도미노부터 끝 도미노까지 쓰러진다는게 증명됨

 

재귀 함수와 수학적 귀납법이 작동원리가 비슷한데?

 

 

두 개는 작동방식이 비슷한 거일뿐 같지 않다.

 

막말로, 임의의 자연수의 합을 구하는 코드를 짠다고 할 때, 이걸 재귀함수로 구현할지 for문으로 구현할지

 

프로그래머 맘이다. 근데, 수학적 귀납법을 사용하면 코드 한줄로도 구현이 가능하다.

 

• 자연수 n까지의 합을 모두 구하는 1 + 2 + ... + (n - 1) + n = n ( n + 1 ) / 2 라는 공식이 있음
• 이걸 수학적 귀납법으로 증명 가능하다.
• S(n) = 1 + 2 + ... + (n - 1) + n 로 두면
• S(n) = n ( n+1) / 2 이란 명제를 P(n)으로 둘 수 있다.
• 그러면 P(0)이 참임을 증명하고
• P(k) → P(k + 1) 이 참이라는걸 증명하면 끝이다.