수학적 귀납법

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

수학적 귀납법(數學的歸納法, 영어: 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라는 것에 모순이 된다. 따라서 원하는 결론을 얻는다.

또한, 페아노 공리계에 의해 자명하게 여겨지기도 한다. 임의의 집합 A에 대하여, 1\in A이고 n\in A일때, n+1\in A이면 A\in \mathbb{N}라는 공리이다.

[편집]

밑에서 서술될 가장 작은 n개의 홀수들의 합이 n^2이 된다는 사실을 증명한다.

일단 1이 명제를 성립시킴을 보인다. 가장 작은 1개의 홀수의 합은 1이고, 1^21 이므로 1은 명제를 만족한다.

임의의 수 k가 명제에 대해 성립한다 가정하면, \overbrace{1+3+5+\cdots+(2k-3)+(2k-1)}^{k} = k^2이다. 이제 이 등식이 성립한다는 전제 하에 k+1에 대해 성립함을 보인다. 양변에 (2k+1)을 더하면 \overbrace{1+3+5+\cdots+(2k-1)+(2k+1)}^{k+1} = k^2 + 2k + 1이다. 우변을 인수분해 하면 (k+1)^2이 되는데, 이는 (k+1)의 제곱이므로 k+1에 대해 성립한다.

그러므로 명제 가장 작은 n개의 홀수들의 합이 n^2가 모든 자연수 n에 대해 성립함을 증명하였다.

또한, 가장 작은 n개의 자연수의 합이 \frac{n(n+1)}{2}임을 증명하는 것도 쉽다.

n=1일때, 가장 작은 n개의 자연수의 합은 1이고, \frac{1(1+1)}{2} = 1이므로 등식이 성립한다.

k가 명제에 대해 성립한다 가정하면, \overbrace{1+2+3+\cdots+(k-1)+(k)}^{k} = \frac{k(k+1)}{2}이다. 이 가정 하에 k+1이 성립함을 보이려면 양변에 k+1을 더한다.

그러면 \overbrace{1+2+3+\cdots+(k-1)+(k)+(k+1)}^{k+1} = \frac{k(k+1)}{2} + (k+1)이다. 여기서 \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}임을 증명함을 된다. (우변이 식 \frac{k(k+1)}{2}에 대하여 kk+1을 대입시켰음을 주목하라.) 좌변을 통분하고 전개한다. \frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{k(k+1)+2(k+1)}{2} =  \frac{(k^2 +k)+(2k+2)}{2} =  \frac{k^2 +3k+2}{2}이다. 이를 인수분해하면 \frac{k^2 +3k+2}{2} = \frac{(k+1)(k+2)}{2} 이다. 즉 k가 성립할때 k+1이 성립한다. (또는, 반대로 \frac{(k+1)(k+2)}{2}을 전개하여 같음을 보일 수도 있다.)

그러므로 명제 가장 작은 n개의 자연수의 합이 \frac{n(n+1)}{2}가 모든 자연수 n에 대해 성립함을 증명하였다.

확장[편집]

일반적인 수학적 귀납법의 형태는

  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)도 성립

등을 증명하기도 한다.

역사[편집]

아래의 문단에 한국어로 번역되지 않은 내용이 담겨 있습니다. 번역되지 않은 부분은 번역을 마치거나 삭제해주어야 합니다.

This section needs to be translated into Korean. Untranslated parts of the section should be rewritten in Korean or eliminated.

최초로 수학적 귀납법이 사용된 예는 유클리드의 소수의 무한성에 대한 증명이나 바스카라 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.