수학적 귀납법(Mathematical induction) 이란?

수학적 귀납법은 무엇인가?

수학적 귀납법을 최초로 사용한 역사상의 인물은 유클리드(Euclid)로 알려져 있습니다. 유클리드는 13권으로 된 원론(Elements)의 제9권 명제 20에서 소수의 무한성을 증명하기 위한 간접증명방법으로 수학적 귀납법을 이용하였습니다. 또한 아르키메데스(Archimedes)는 자신이 고안한 착출법으로 곡선의 면적을 계산하는 데 수학적 귀납법을 사용하였고, 이후로 남아 있는 기록에 의하면 이탈리아의 모롤리꼬(Francesco Maurolico)가 논문에서, 이어서 파스칼(Blaise Pascal), 페르마(Pierre de Fermat), 베르누이(Jakob BBernoulli) 등도 수학적 귀납법을 증명방법으로 사용하였습니다.

 

수학적 귀납법(mathematical induction)이 무엇인지 알아보기 위해 자연수 집합 N에 대하여 생각해 봅시다.

자연수는 1에서부터 시작하여 2, 3, 4,...로 이루어져 있습니다. 그런데 2는 1에 1을 더한 것이고, 3은 2에 1을, 4는 3에 1을 더하는 방식으로 자연수를 구성해 나갈 수 있습니다. 일반적으로 어떤 자연수에 1을 더하면 또 다른 자연수를 얻게 되는 법칙에 의하여 자연수의 집합 N이 이루어져 있다고 말할 수 있습니다. 귀납적 집합이란 1을 더하는 연산이 닫혀있는 집합이라고 말할 수 있습니다.

자연수의 집합 N이 가지고 있는 하나의 큰 특징으로는 수 1을 원소로 갖고 있다는 것입니다. 그러나 실수 집합, 정수 집합은 수 1을 가지고 있으면서 자연수가 아닌 훨씬 많은 수들을 가지고 있어서 자연수 집합 N과는 다른 집합입니다. 따라서 이러한 사실로부터 “N은 1을 갖고 있는 최소의 귀납적 집합이다”라고 말할 수 있습니다.

 

이제는 자연수의 집합 N에 관한 공리를 수학적 귀납법으로 바꾸어 생각해 봅시다. 

 

1을 원소로 가지는 귀납적인 집합은 어느 집합이라도 모든 자연수를 포함한다.

 

이러한 공리를 바탕으로 하면 자연수 집합 N은 1을 원소로 갖는 최소의 집합임을 알 수 있습니다. 수학적 귀납법은 자연수의 집합 N에 관한 정리를 증명할 때 유용하게 사용됩니다.

 

도미노와 수학적 귀납법

도미노는 주사위 놀이에서 유래된 놀이입니다. 18세기 이탈리아에서 처음 고안된 이래 프랑스, 벨기에의 카페, 영국의 바에서 애용되었으며, 미국의 서부에서는 많은 회원을 가진 클럽이 있기도 합니다. 도미노의 앞은 상아, 뒤는 흑단으로 만들어졌으며 게임을 하기 위해서는 주사위처럼 1에서 6까지의 점이 새겨진 28개의 패를 사용합니다.

 

도미노라는 말은 원래 성직자용의 검은 법의를 뜻하는 말입니다. 이러한 도미노를 게임으로 즐기기 위한 방법으로 여러 가지가 있는데 그중에 하나의 방법이 도미노 패를 일정한 간격으로 세웠을 때 처음의 패가 넘어지면 나머지 것들도 차례로 모두 넘어지는 것이 있습니다. 도미노 이론은 미국이 베트남 전쟁에 개입할 당시의 이론적인 근거가 되기도 하였습니다. 바로 이 도미노 이론의 내용이 수학적 귀납법의 핵심입니다. 수학적 귀납법은 직관적이고 순환적인 패러다임과 관련이 있습니다.

순환적인 패러다임은 한 가지 경우와 그 앞의 경우 사이의 관계를 찾아내는 것으로 이러한 접근 방법은 앞에 있는 도미노가 그다음의 도미노를 쓰러뜨릴 정도로 충분히 가까이 높여 있다는 사실을 보이는 것과 같습니다. 또한 직관적인 패러다임은 맨 첫 번째 도미노로부터 반복적으로 일어나는 패턴을 찾아내는 것으로 이러한 접근방법은 첫번째 도미노가 넘어지면 이어서 그다음 도미노들이 차례로 넘어짐을 보이는 것과 같습니다. 

이러한 수학적 귀납법은 주어진 어떤 문제에서 그 문제가 갖고 있는 관계식으로부터 알고리즘을 만들고 해를 찾아내는 데 있어서 찾아낸 알고리즘과 해가 과연 옳은지를 판정할 수 있게 해 줍니다. 수학적 귀납법은 통상적으로 과학자들이 사용하는 과학적귀납법과는 다르다고 할 수 있습니다. 그 이유는 수학적귀납법은 엄밀한 증명을 위한 하나의 형식으로, 연역법의 한 가지 특별한 경우이기 때문입니다.

 

수학적 귀납법은 증명방법으로 사용되는 것과 마찬가지로 정의방법으로도 사용됩니다. 예를 들어, n!을 정의하는 일반적인 방법으로 다음과 같이 귀납적으로 정의합니다.

 

                              (1) 1 ! = 1

                              (2) n > 1 에 대하여 n ! = n(n-1) !

 

이 두 조건은 n!의 정의가 모든 양의 정수 n에 대하여 일일이 열거되는 법칙을 말해주고 있습니다.

 

수학적 귀납법이 양의 정수에 관한 명제를 증명하는 데 있어서 표준적인 방법으로 사용되고 있기는 하지만 명제 자체를 만들어 낼 수는 없다는 단점을 가지고 있습니다. 물론 우리가 일반적으로 성립하는 성질을 유추해 낼 수 있을 때에는 그 성질이 성립하는지 그렇지 않은지를 귀납법을 통하여 보일 수 있습니다.

 

명제 p(1), p(2), p(3), ...를 각각 도미노로 생각해 봅시다. 우리가 귀납 과정을 증명한다는 것은 모든 도미노가 넘어지면서 그다음의 도미노를 넘어뜨림을 보이는 것입니다. 즉, p(1)을 보이면 맨 처음의 도미노가 넘어지는 것이므로, p(1)과 귀납단계를 증명하면 우리는 모든 도미노를 넘어뜨리게 되는 것입니다.

 

이와 같은 종류의 분석을 통하여 우리는 과정을 이해하고 증명의 핵심이 무엇인지 알 수 있습니다. 귀납적 단계를 설명해 주는 핵심적인 사항은 결론 부분이 어떻게 가정과 관계를 갖는가? 하는 것을 아는 것입니다. 귀납적인 단계를 증명하는 데 있어서 우리는 명제 p(t+1)이 명제 p(t)와 어떠한 관계를 갖는지, 다시 말하면 p(t)가 참이라는 사실이 p(t+1)이 참임을 보이는데 어떻게 도움이 되는지를 알아야 합니다. 만일 우리가 두 명제 사이의 관계를 이해할 수 있다면 우리는 어떻게 증명을 해야 하는지 또한 쉽게 알 수 있게 됩니다. ■