5. 수학적 귀납법(3-1)

수학적 귀납법

1. 증명의 방법론

정의1

증명(proof)이란  논리적  법칙을  이용하여  주어진  가정으로부터  결론을  유도해내는  추론의  한 

방법으로서, 어떠한 명제나 논증이 적절하고 타당한지를 입증하는 작업이다. 

. 공리(axiom): 별도의 증명 없이 참(true)으로 사용되는 명제 

. 예  :  ‘1은 자연수이다.’는  ‘n이 자연수이면  n+1도 자연수이다.’라는 

명제의 공리 

. 정리  (theorem)  : 참으로 확인된 명제 

. 하나의 명제를 참으로 확정하는 과정을 증명(proof)이라고 한다. 

. 수학이나 컴퓨터와 관련된 여러 분야에서도 증명 과정은 매우 중요 

. 소프트웨어를 개발하는 과정에서는 프로그램 검증 과정을 통해 프로그램 

 오류를 줄이고, 빠른 시간 안에 정확한 프로그램을 개발할 수 있게 함. 

. 증명은 다양한 분야의 개념을 확립할 때 중요한 역할 담당 

. 증명의 종류  : 수학적 귀납법, 직접 증명법, 간접증명법 등 

. 연역법(deduction) 

: 주어진 사실들과 공리들에 입각하여 추론을 통하여 새로운 사실을 도출하는 것 

.귀납법(induction) 

: 관찰과 실험에 기반한 가설을 귀납추론을 통하여 일반적인 규칙을 입증하는 것

. 명제  p1,  p2,  p3,  …,pn이 사실이라고 할 때  pn+1의 경우에도 성립한다는 것을 보이게 된다. 

따라서  n이  1인 경우에 성립하는 것을 보이고 또한 모든 양의 정수  n에 대해 성립한다고 가정

하면 n+1의 경우에도 성립하는 것을 보여주면 된다. 

.  여기서  출발점이  되는  n의  값을  기본  단계(basis)라고  하며,  p1,  p2,  p3,…,pn  을  귀납가정

(inductive  assumption),  pn+1  의  경우에  성립됨을  보이는  것을  귀납단계(inductive  step)라고 

한다. 

. 논리식 증명에 이용되는 경우 

. 모든 정수  n에 대해 어떤 명제  p(n)이 주어졌을 경우  p(n)이  n≥1인 모든 정수에 대해 참이라

는 것을 증명하기 위한 방법은 다음과 같다. 

  (1) 기본 단계(basis)  : p(1)이 참임을 보인다. 

  (2) 귀납가정(inductive  assumption)  :  p(n)이 참이라고 가정한다. 

  (3)  귀납단계(inductive  step)  :  명제  pn  이  참이라고  할  때(즉,  귀납가정에  입각하여)  p(n+1) 

이 참임을 보인다. 

제  2 수학적 귀납법  / 강한 귀납법(Strong  Induction) 

어떤 정수  n 에 관한 명제 p(n)에 대하여 다음 두 조건이 성립한다고 하자. 

(1) p(1)은 참이다. 

(2) 임의의 정수  k ≥1에 대해  p(1)∧p(2)∧…∧ p(k) 참이면 p(k+1)도 참이다. 

이 때 정수n에 대하여  p(n)은 참이다. 

. 제2 수학적 귀납법을 이용한 증명은  p(1),p(2),  …,  p(k)가 모두 참임을 이용하여  p(k+1)도 참

이 됨을 보이면 된다.