Mathematical Induction, Proof by Induction   수학적 귀납법

(2018-03-02)

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

1. 수학적 귀납법

  ㅇ 어떤 결과를 증명하는데 사용되는 유용한 증명 방법 중 하나
     - 특정 명제가 참 이라는 사실로부터, 일련의 명제들이 참 임을 밝혀(추론해)내는 증명
2. 수학적 귀납법의 구성,방법,사용예증명 구성
     - 귀납 가정(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)도 참임을 보임

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


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

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

  ㅇ 공식이나 정리를 발견하거나 직관을 얻기위해 사용되지는 않음
     - 다만, 부분적인 사실들로부터 전체를 추론해 보는 방식에는 응용될 수 있음

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


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

 
        최근수정     요약목록(시험중)     참고문헌