수학적 귀납법 mathematical induction

수학적 귀납법(영어 mathematical induction)은 고등학교 수학 시간에 이미 배우는 내용입니다.

 

귀납적으로 증명 가능한 수학 문제의 증명 기술로 쓸 수 있습니다.

 

그러나 배운지 너무 오래되었다는 점, 그리고 고등학교 수학 과정 중에는 증명문제를 많이 연습할 기회가 없다는 점 때문에 잊어버렸습니다.

 

대학원 강의 중 수학적 귀납법을 이용한 숙제가 나와서 복습했습니다.

 

복습에 사용한 교재는 한양대학교 컴퓨터공학과 도경구 교수님께서 번역해주신 알고리즘 기초(홍릉과학) 책의 부록 부분을 참고했습니다.

 

복습하시려는 분은 혹시 고등학교 수학 책을 갖고 계시다면 직접 확인해보시면 쉽게 이해할 수 있을 겁니다(현재 교육과정에서는 고등학교 1학년 2학기 중간고사 이후 부분에 다룹니다).

 

예제를 들어 수학적 귀납법을 알아보겠습니다.

위 공식이 참일까요?

참이라면 어떻게 증명할까요?

n = 1, 2, 3, … 을 대입해보면

n = 1일 때,

n = 2일 때,

n = 3일 때,

이런 식으로 n 을 1씩 늘려가서 무한대까지 늘려가면 이 공식은 항상 성립한다고 할 수 있을까요?

 

위 예는 각각 n=1, 2, 3일 경우만 보여주고,

위 공식에 관한 완벽한 증명은 될 수 없습니다.

 

수학적 귀납법으로 증명하는 방법은 세 단계(또는 두 단계. 위키피디아에서는 두 단계로 합니다)로 나누어 할 수 있습니다.

 

각 단계는 (1) 귀납의 기본(induction base), (2) 귀납의 가정(induction hypothesis), (3) 귀납적 증명(induction step)입니다.

 

(1)번 단계에서 증명할 문제가 당연하게 참인 첫 번째 단계를 제시합니다.

(2)번 단계에서 증명할 일반적인 명제가 n번째 경우에서 참이라고 가정합니다.

(3)번 단계에서 증명할 일반적인 명제가 n+1번째 경우에서 참인 것을 증명합니다. 그러면 귀납적 추론에 따라 (2)번 단계에서 가정한 명제가 참입니다.

 

위 세 단계만 따르면 귀납적 증명, 쉽게 할 수 있습니다.

 

앞서 예시로 들었던 공식을 다시 수학적 귀납법에 따라 증명해보겠습니다.

(1) 귀납의 기본(induction base):

n = 1일 때,

으로 참입니다.

(2) 귀납의 가정(induction hypothesis):

이 참이라고 가정합니다(위 식을 식(a)라고 하겠습니다.

(3) 귀납적 증명(induction step):

이 참이면(위 식을 식(b)라고 하겠습니다), 귀납적 추론으로 (2)의

가 참이 됩니다.

참인지 알아볼까요?

식 (b)를 귀납적 가정(induction hypothesis)에서 참이라고 가정했으므로 식(a)에 따라 다음과 같이 변형할 수 있습니다.

이 때,

이므로, 식 (b)

이고, 귀납적 추론에 따라 우리가 가정한 식 (a)

는 참입니다.

알고리즘 기초 국내도서 저자 : Richard Neapolitan,Kumarss Naimipour / 도경구역 출판 : 홍릉과학(홍릉과학출판사) 2014.01.20 상세보기

참고 링크: https://en.wikipedia.org/wiki/Mathematical_induction#Example