2013년 9월 14일 토요일

수학적 귀납법(數學的歸納法: mathematical induction)

수학적 귀납법(數學的歸納法, 영어: mathematical induction)은 수학에서 어떤 주장이 모든 자연수에 대해 성립함을 증명하기 위해 사용되는 방법이다. 무한개의 명제를 함께 증명하기 위해, 먼저 '첫 번째 명제가 참임을 증명'하고, 그 다음에는 '명제들 중에서 어떤 하나가 참이면 언제나 그 다음 명제도 참임을 증명'하는 방법으로 이루어진다.
보다 일반적으로, 이는 모든 서수의 집합에 대해 초한귀납법으로 확장할 수 있으며, 임의의 기초관계에 대해 구조적 귀납법으로 확장할 수도 있다. 수학적 귀납법은 자연수 집합에서 정렬순서원리와 동치이다.
수학적 귀납법은 이름과는 달리 귀납적 논증이 아닌 연역적 논증에 속하며, 따라서 이는 명확하고 엄밀한 증명 방법이다. 그러나 의미에 혼란이 없을 때에는 수학적 귀납법을 줄여서 귀납법이라고 부르기도 한다.

수학적 귀납법의 원리

수학적 귀납법의 원리는 자연수 집합 \mathbb{N}의 부분집합을 S 라 할 때, 두 조건
  • 1\in S
  • k\in S이면 k+1\in S
을 만족하면 S=\mathbb{N} 이라는 정리이다.

증명

귀류법으로 증명한다. 먼저 S\not=\mathbb{N} 이라고 가정하자. 그러면 S 는 \mathbb{N} 의 진부분집합이므로, \mathbb{N}-S\not=\emptyset 이다. 따라서 자연수의 정렬성에 의해 \mathbb{N}-S의 최소원 m이 존재한다. 이때 1\in S이므로 m>1이다. 따라서 m-1\in S이므로, 두 번째 조건에 의해 m\in S이다. 이는 m\not\in S라는 것에 모순이 된다. 따라서 원하는 결론을 얻는다.

확장

일반적인 수학적 귀납법의 형태는
  1. P(1)이 성립
  2. P(n)이 성립하면 P(n+1)도 성립
을 증명하지만 이를 확장하여,
  1. P(1)이 성립
  2. P(2)가 성립
  3. P(n)이 성립하면 P(n+2)도 성립
  1. P(1)이 성립
  2. P(2)가 성립
  3. P(n), P(n+1)이 성립하면 P(n+2)도 성립
  1. P(1)이 성립
  2. P(1), P(2), ..., P(n)이 성립하면 P(n+1)도 성립
등을 증명하기도 한다.

역사최초로 수학적 귀납법이 사용된 예는 유클리드의 소수의 무한성에 대한 증명이나 바스카라 2세의 "순환 방법"(cyclic method) 등에서 찾을 수 있다.".[1] 알카라지는 1000년 경에 쓴 책에서 이항 정리 등을 증명하기 위해 수학적 귀납법의 한 형태를 사용했다.[2] [3] 그러나 이들은 수학적 귀납법을 자신이 사용한 가정으로서 명확히 밝히지 않았으며, 처음으로 귀납법에 대한 엄밀한 서술을 한 이는 프란체스코 마우롤리코 (Francesco Maurolico)로, 그는 1575년의 저서 〈Arithmeticorum libri duo〉에서 이를 이용해 가장 작은 n개의 홀수를 더하면 n2이 됨을 증명했다. 스위스의 야콥 베르누이와 프랑스의 블레즈 파스칼 및 피에르 드 페르마도 귀납법을 독립적으로 발견했다.[1]


  1. ↑ 가 나 Cajori (1918), p. 197
    The process of reasoning called "Mathematicla Induction" has had several independent origins. It has been traced back to the Swiss Jakob (James) Bernoulli, the Frenchman B. Pascal and P. Fermat, and the Italian F. Maurolycus. [...] By reading a little between the lines one can find traces of mathematical induction still earlier, in the writings of the Hindus and the Greeks, as, for instance, in the "cyclic method" of Bhaskara, and in Euclid's proof that the number of primes is infinite.
  2. ↑ Katz (1998), p. 255-259.
    Another important idea introduced by al-Karaji and continued by al-Samaw'al and others was that of an inductive argument for dealing with certain arithmetic sequences.
  3. ↑ (영어) O’Connor, John J.; Edmund F. Robertson (1999년 7월). Abu Bekr ibn Muhammad ibn al-Husayn Al-Karaji. 《MacTutor History of Mathematics Archive》. 세인트앤드루스 대학교.
    Al-Karaji also uses a form of mathematical induction in his arguments, although he certainly does not give a rigorous exposition of the principle.

Wikipedia

 

 

작성자: 시간:

댓글 없음:

댓글 쓰기

피드 구독하기: 댓글 (Atom)