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

(2019-12-18)

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

1. 귀납적 사고 (Inductive Thinking)

  ㅇ 통상, 공식이나 정리를 발견하거나 직관을 얻기위해 사용되지는 않으나,
     - 문제의 파악이나 이해에 도움이 되며,
        . 크기는 다르지만, 동일 성격의 문제들 간의 관계에 의해 문제를 파악

  ㅇ 주로, 부분적인 사실들로부터 전체를 추론해 보는 방식에 폭넓게 응용 가능
     - 관찰과 실험을 통해 얻어진 부분적이고 특수한 사례를 근거로,
     - 이를 전체에 적용시키는 이른바 '귀납적 비약'을 통해 이루어짐

  ※ 위대한 과학자들의 사유 방법 : 단순성의 원칙 
     - 복잡한 현상을 단순한 기본 개념/관계로 되돌리며,
        . 즉, 귀납(歸納)시키려는 시도를 하곤 함

     * 한편, 귀납적 분류 이란?
        . 자연 현상을 몇가지의 단순한 분류로 귀납시키려는 것


2. 수학적 귀납법 (Mathematical Induction) 이란?

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

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

  ㅇ [수학적 귀납법의 활용]
     - 어떤 결과를 증명하는데 사용되는 유용한 증명 방법 중 하나
     - 개별 사실들을 기초(증거)로 하여 일반 결론을 끌어내는 논증 방법


3. 수학적 귀납법의 논증 구성,방법,사용예

  ㅇ 개요
     - 특정 명제들이 참 이라는 사실로부터, 
     - 일련의 명제들이 참 임을 밝혀(일반 결론을 추론해)내는 증명법

  ㅇ 증명 구성
     - 귀납 가정(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)도 참임을 보임

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


[추론,논증] 1. 추론 2. 증명 3. 귀납법 4. 귀류법 5. 연역법

 
        최근수정     요약목록     참고문헌