Mathematical Induction   수학적 귀납법

(2017-03-25)

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

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. 명제함수,술어논리학
  1.   기술공통
  2.   기초과학
        1. 과학
    1.   수학
      1.   기초수학
      2.   집합,논리
        1.   집합
        2.   논리와 증명
          1.   1. 논리(Logic),수리 논리학
              2. 논리식
              3. 명제(proposition)
              4. 공리(axiom)
              5. 정리(theorem)
              6. 정의(definition)
              7. 증명(proof)
              8. 수학적 귀납법
              9. 동치(equivalence)
              10. 명제함수,술어논리학
        3.   관계
      3.   정수론(수론)
      4.   해석학(미적분 등)
      5.   대수학
      6.   확률/통계
      7.   수치해법
    2.   물리/화학
    3.   지구,천체 과학
    4.   생명과학
  3.   파동/광학/음향
  4.   방송/멀티미디어/정보이론
  5.   전자/전기/제어
  6.   통신/네트워킹
  7.   정보기술(IT)
  8.   기계/재료/공업일반
  9.   표준/계측/품질
  10.   기술경영

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