Mathematical Induction   수학적 귀납법

(2017-03-25)

Principle of Mathematical Induction, 수학적 귀납법 원리

기초과학 1. 과학

수학
물리/화학
지구,천체 과학
생명과학
 > 수학기초수학
집합,논리
정수론(수론)
해석학(미적분 등)
대수학
확률/통계
수치해법
 > 집합,논리집합
논리와 증명
관계
 > 논리와 증명 1. 논리(Logic),수리 논리학
2. 논리식
3. 명제(proposition)
4. 공리(axiom)
5. 정리(theorem)
6. 정의(definition)
7. 증명(proof)
8. 수학적 귀납법
9. 동치(equivalence)
10. 명제함수,술어논리학

     
1. 수학적 귀납법

  ㅇ 어떤 결과를 증명하는데 사용되는 유용한 증명 방법

  ㅇ 증명 구성
     - 귀납 가정(induction hypothesis)      : 임의의 k에 대해 P(k)가 참이라는 가정
     - 귀납 기초(induction base,basis step) : P(1)이 참임을 증명
     - 귀납 절차(induction step)            : P(k)가 참일 때, P(k+1)도 참임을 보이는 증명

  ㅇ 증명 방법
     - 두 단계(귀납기초,귀납절차)의 증명을 차례로 완성함
        . ①  P(1)이 참 임을 증명
        . ②  모든 임의 k(k≥1)에 대하여,  P(k) ⇒ P(k+1)이 참(true) 임을 증명
           .. 즉, 임의 k에 대해 P(k)가 참이라 가정하고, 이 가정하에 P(k+1)도 참임을 보임

  ㅇ 사용 例
     - 급수 공식, 항등식, 부등식, 알고리즘 복잡성 등에 대한 결과를 증명하는데 쓰임
        . 수열재귀적으로 정의할 때, 이 수열을 귀납법으로 증명할 수 있음 등


2. 수학적 귀납법 특징/역사

  ㅇ 매우 중요한 수학적 기초
     - 증명의 한 가지 방법으로 이용되고 있음

  ㅇ 단, 공식이나 정리를 발견하거나 직관을 얻기위해 사용되지는 않음

  ㅇ [수학적 귀납법 역사]
     - 최초 엄밀한 증명 사례 : 1575년 Francesco Maurolico 
     - 최초 용어 사용        : 1838년 Augustus De Morgan


[ 논리와 증명 ]1. 논리(Logic),수리 논리학  2. 논리식  3. 명제(proposition)  4. 공리(axiom)  5. 정리(theorem)  6. 정의(definition)  7. 증명(proof)  8. 수학적 귀납법  9. 동치(equivalence)  10. 명제함수,술어논리학  

 
        최근수정     모바일웹     참고문헌