수학적 귀납법

數學的 歸納法 / mathematical induction

자연수에 관한 명제 $P(n)$이 모든 자연수(또는, 어떤 자연수보다 큰 모든 자연수)에 대하여 성립함을 보이는 증명법이다.[1]

귀납법이라는 이름 때문에 혼동하기 쉽지만, 엄밀히 말하면 연역논증의 일종이다. 수학적 연역법 하지만 수학적 귀납법의 역사가 기원전으로 거슬러 올라감을 고려하면, 수학적 귀납법이 연역 논증이라는 것은 현대적 재해석이고 역사적으로 따졌을 때 과거엔 실제로 귀납법이었다고 말할 여지가 있다.

보통 증명 시에는 단순히 귀납법(induction)이라고만 쓴다. 예를 들어, "By induction on (...)"라고 쓰고 수학적 귀납법을 전개하는 식. 몹시 자주 쓰이는 주제에 풀네임은 쓸데없이 길어서 그런 것도 있고, 어차피 수학적 증명에서는 '귀납법'이 안 쓰이니까 오해의 소지가 없기도 하다.

증명은 두 부분으로 구성되는데, 첫 번째 부분은 최소원 $n=n_0$에 대해 $P(n_0)$가 성립함을 보이는 부분이며, 두 번째 부분에서는 임의의 자연수 $k$에 대해 $P(k)$가 성립한다는 가정 하에 $P(k+1)$ 또한 성립함을 보이게 된다.

영어로는 흔히 위의 첫 번째 부분을 basis step, $n$에 대한 임의의 상수 $k$를 가정하는 부분을 assumption step, 두 번째 부분인 $k+1$ 또한 $n$에서 성립함을 보이는 부분을 inductive step, 마지막 결론을 도출하는 부분을 (즉, '따라서 $n$에 대한 (수학적) 귀납법에 의하여 해당 명제는 참이다'라고 하는 부분을) conclusion step이라 한다. 또한, assumption step에서 쓴 가정을 흔히 귀납적 가정, 영어로는 induction hypothesis라고 부른다. 하지만 assumption step과 conclusion step은 워낙 전형적이기 때문에 실제 증명에서는 매우 간단하게 서술되는 경우가 많다. 심지어, assumption step을 쓰는 둥 마는 둥 대충 쓰고 conclusion step은 아예 글로도 옮기지 않는 경우가 왕왕 있다. 예를 들어 이 페이지의 증명을 살펴보자.[2] 물론, 저 둘 역시 수학적 귀납법의 핵심 구성 요소이긴 하지만, 대충 써도 사람들이 귀납법으로 알아먹고 알아서 생략된 내용들을 읽어낼 수 있기 때문에 (예컨대, 그래도 'induction hypothesis'라든가 'By induction on [...]' 정도는 언급해 주니까 그걸로 상황 파악을 충분히 할 수 있긴 하다) 이런 생략들이 가능해지는 것이다. 물론, basis step과 inductive step은 trivial하다고 말하고 끝날 정도로 짧을지언정 생략까지 하는 일은 없다. 그래서 'assumption step'과 'conclusion step'은 따로 언급되는 일이 거의 없긴 해도, 두 basis step과 inductive step 이 두 용어는 종종 쓰이기 때문에, 예컨대 증명 끝나고 다른 내용에서 "이 증명의 inductive step을 보면 ..." 하는 식으로 언급이 되긴 하므로, 이 두 용어들을 잘 기억해 두는 것이 좋다.

전제하는 원리는 다음과 같다.

이 두 가지 성질을 만족하면 집합 $X$는 집합 $\mathbb{N}$과 같다는 성질, 즉 페아노 공리계를 이용한다.[3]

이때, $P(n)$이 모든 자연수에 대하여 성립함을 보이기 위해 다음 2가지만 보이면 된다.

그러면 명제 $P(n)$을 만족하는 자연수 $n$들의 집합을 $X$라고 할 때, $X$는 자연수의 집합 $\mathbb{N}$과 같아지므로 모든 자연수 $n$에서 $P(n)$이 성립한다.

수학적 귀납법과 동치이지만 뭔가 조건이 좀 더 강해보이는 강한 수학적 귀납법이라는 것도 있다. 구체적으로는 $P(n)$이 성립하는 것을 확인하기 위해서는 다음을 증명하면 된다. 하지만, 본질적으로 수학적 귀납법과 동일하다.

실제 증명에서는 원래 수학적 귀납법 못지않게 강한 수학적 귀납법을 자주 사용한다. 많은 경우 $P(n+1)$을 보이기 위해 $P(n)$이 성립할 때 생기는 무언가보다 $P(1),\,P(2),\,\cdots,\,P(n)$ 중 어떤 하나에서 생기는 무언가를 쓰는 게 더 적절하기 때문이다.[5] 조건이 강해 보여서 쓰기 불편해 보이겠지만 그건 큰 오해이다. 원래 수학적 귀납법의 것보다 더 잔뜩 가정해 놓고[6] 그 중에 원하는 거 아무 거나 한두 개 골라 쓰는 것인데도 페널티가 생기기는커녕 이게 원래 수학적 귀납법과 사실 상 동치이니, 오히려 더 편리한 녀석이라고 할 수도 있다.

많은 경우 1번 스텝보다 2번 스텝을 보이는 게 훨씬 더 어렵다. 사실 1번 스텝은 많은 경우 '자명하다' 한 마디로 끝내도 좋을 정도이다. 예를 들어 $n$이 어떤 벡터 공간의 차원이면 이런 상황이 자주 발생한다. 즉, $n = 1$일 때 다루는 대상이 엄청 단순하거나 매우 구체적이면 1번 스텝 역시 단순해진다. 하지만 물론 1번 스텝이 항상 그렇게 쉬운 단계이진 않다. 오히려 경우에 따라선 1번 스텝이 훨씬 더 어려워지고 2번 스텝은 단순해지는 경우도 종종 발생한다.[7]

정수론에서 가장 중요한 증명법 중에 하나이다. 단점은, 범위가 자연수(혹은 확장한다고 해도 정수)에서만 성립한다는 것이다.[8] 초한귀납법이 있긴 하지만 생각보다 그리 자주 쓰이지는 않는다. 그럼에도 수학적 귀납법은 정수론 뿐만 아니라 많은 분야에서 쏠쏠히 잘 쓰이는데[9], 많은 수학적 대상들이 자연수로 된 핵심적인 파라미터(parameter)를 가지기 때문이다. 다항식의 차수라든가 유한 차원 벡터 공간의 차원[10][11], 그리고 수열[12]의 인덱스가 가장 대표적인 예이다. 그리고 이런 대상들이 정수론, 대수학은 물론 기하학, 해석학, 위상수학을 포함한 수학 전반에서 몹시 자주 나타나고, 이들 혹은 이들을 활용한 어떤 대상의 성질을 규명할 때 이들 자연수 파라미터가 핵심으로 작용하니, 수학적 귀납법은 유한귀납법만 있어도 어디에서든 강력한 도구로 활용된다.

사실 증명 과정에서 은연중에 수학적 귀납법을 쓰는 경우가 많다. 예를 들어 어떤 작업을 한 다음, 뭔가 더 작은 것이 나왔고 (여기에다 이해를 돕기 위해 한 번 더 비슷한 작업을 할 수도 있지만) 그 다음에 "... 이 작업을 (그 작은 것에) 계속 반복하다 보면..."라고 쓰는 경우가 왕왕 있는데, 여기서 수학적 귀납법을 썼다고 보면 된다. 사실 이런 반복 작업을 수학적으로 형식화한 것이 바로 수학적 귀납법이다.

수학적 귀납법도 다변수함수처럼 다차원 수학적 귀납법, 다변수 수학적 귀납법을 상정해 볼 수 있다. 하지만 파라미터 하나에 대한 수학적 귀납법을 영역전개한 다음, 그 영역 안에서 또다른 파라미터에 대한 또다른 수학적 귀납법을 영역전개하면 그것만한 인외마경(...)을 보기도 어려울 정도로 증명이 복잡해진다.[13] 사실, 그럴 일이 생길 것 같으면 안 쪽의 수학적 귀납법이 다루는 내용을 보조정리(lemma)로 따로 빼 놔서 따로 다룬 다음, 그 결과를 적용시키는 식으로 분리해서 다루는 것이 보통이다. 다행스럽게도 이런 분리가 가능한 경우가 보통이다. 하지만 안쪽의 수학적 귀납법을 증명하기 위해 바깥쪽의 수학적 귀납법으로 가정한 내용을 가져다 써야 하는 경우가 생기면, 그런 분리가 어려울 수 있다.[14]

주어진 명제에 대하여,

즉, $n=1$의 경우 성립한다. $n$이 성립하면, $n+1$이 성립한다. 여기서 $n=1$로 둘 때 $n+1=2$에서 성립한다. 또 여기서 $n=2$에서 성립하므로 $n+1=3$에서도 성립한다. 이하 무한 반복. 이렇게 하면 무한대까지 쭉쭉 뻗어나가 모든 자연수에서 성립한다는 것이다.

이것을 수학적인 표현을 사용하면

위의 귀납법을 이에 대비하여 약한 귀납법이라고도 한다. 이는 약한 귀납법과 동치임이 알려져 있지만, 약한 귀납법보다 강력하다. 이 단락에서는 구분을 위해 모두 약한·강한 귀납법이라고 명시할 것이다. 강한 귀납법은 완전 귀납법(Complete Induction)으로도 불린다.

자연수를 확장한 서수(초한서수), 기수(초한기수)에 대해서 적용하기 위해서, 수학적 귀납법을 확장한 것이다.

이 세 가지를 하나의 문장으로 묶을 수 있다. $A$가 well-ordered class(모든 부분집합의 상한이 존재하는 집합)이고, $P(x)$를 각각의 원소 $x\in A$에 대해 참과 거짓이 명백한 명제라 하자. 다음 조건이 모든 $x\in A$에 대해 성립한다면, $P(x)$는 모든 원소 $x\in A$에 대해 참이다.

이 조건 아래에서는 가장 작은 원소에 대한 추가적인 조건이 없어도 되는데, 바로 이 조건이 그것을 포함하고 있기 때문이다! 만약 $x_0$를 가장 작은 원소라고 하면, $y<x_0$ 부분이 거짓이 되어 전건의 논리값이 참이 된다. 따라서 $P(x_0)$가 참이다.

枚擧的 歸納法 / enumerative induction

수학적 귀납법과는 또 다른 형태의 완전 귀납법. 수학적 귀납법도 내용을 보면 매거적 귀납법과 공통 분모가 있기는 하지만, 수학적 귀납법에서 증명하는 명제는 '$n=1$에서 성립한다' 와 '$n=a$에서 성립한다면 $n=a+1$에서 성립한다'라는 단 두 가지 명제이기 때문에...

문자 그대로, 특정 집합에 있는 모든 원소에서 해당 명제가 성립함을 모든 원소를 일일이 언급해 가면서 직접 증명하는 방법이다. 하지만 귀납법의 생명이 해당 명제를 일반화할 수 있다는 것, 즉 그 집단에서의 일부분의 성질만 조사하고서도 그 성질을 집단 전체의 성질로 확장할 수 있다는 점,[17] 치명적으로 이전까지의 답이 다음 답은 완전히 보증하지 않는다는 점 때문에, 아리스토텔레스는 매거적 귀납법을 '사이비 귀납법'이라고 불렀다.

$n=1$일 때, 식 $(\ast)$는

으로, 성립한다.

$n=m$일 때,

이 성립한다고 가정하면 $n=m+1$일 때,

이다. 한편, 식 $\small{(\#)}$이 성립하기 때문에

따라서 $k=m+1$일 때도 식이 성립하므로 증명이 끝났다.

$n=1$일 때,

으로, 성립한다.

$n=m$일 때,

이 성립한다고 가장하면, $n=m+1$일 때,

이다.

한편,

그런데, 식 $\small(\#)$이 성립하기 때문에

이므로 $k=m+1$일 때도 성립하므로 증명이 끝났다.

$n=2$일 때

이므로 부등식이 성립한다.

$n=k$일 때

이 성립한다고 가정하자.

한편, $n=k+1$일 때

이때, $\small (\#)$에 의하여


다음을 계산하면

이상에서 다음이 성립한다.

따라서 $n=k+1$일 때도 이 부등식이 성립하므로 증명이 끝났다.